Description
Input
Output
Sample Input
2 7 9 ooo**oooo **oo*ooo* o*oo**o** ooooooooo *******oo o*o*oo*oo *******oo 10 1 * * * o * * * * * *
Sample Output
17 5
题目大意：用1*2的长条覆盖图中的“*”。问最少需要多少个长条。
解题思路：最小路径覆盖：选择最少的边，让每个顶点都被选中，单独的结点可以作为一条路径。建图思路都是奇偶性建图。但是不同的是，这个需要把所有“*”都覆盖。那么我们考虑最小路径覆盖。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 660;
const int INF = 0x3f3f3f3f;
vector<int>G[maxn];
int Mx[maxn], My[maxn], dx[maxn], dy[maxn], used[maxn], dis;
char Map[maxn][maxn];
int lis[maxn][maxn];
bool SearchP(int _n){
queue<int>Q;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
int dis = INF;
for(int i = 1; i <= _n; i++){
if(Mx[i] == -1){
dx[i] = 0;
Q.push(i);
}
}
int v;
while(!Q.empty()){
int u = Q.front(); Q.pop();
if(dx[u] > dis) break;
for(int i = 0; i < G[u].size(); i++){
v = G[u][i];
if(dy[v] == -1){
dy[v] = dx[u] + 1;
if(My[v] == -1){
dis = dy[v];
}else{
dx[My[v]] = dy[v] + 1;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
int dfs(int u){
int v;
for(int i = 0; i < G[u].size(); i++){
v = G[u][i];
if(!used[v] && dy[v] == dx[u] + 1){
used[v] = 1;
if(My[v] != -1 && dy[v] == dis){
continue;
}
if(My[v] == -1 || dfs(My[v])){
Mx[u] = v;
My[v] = u;
return true;
}
}
}
return false;
}
int MaxMatch(int ln,int rn){
int ret = 0;
memset(Mx,-1,sizeof(Mx));
memset(My,-1,sizeof(My));
while(SearchP(ln)){
memset(used,0,sizeof(used));
for(int i = 1; i <= ln; i++){
if(Mx[i] == -1 && dfs(i)){
ret++;
}
}
}
return ret;
}
int main(){
int T, cas = 0, n, m, N, M;
scanf("%d",&T);
while(T--){
n = m = 0;
scanf("%d%d",&N,&M);
for(int i = 0; i <= 210; i++){
G[i].clear();
}
for(int i = 0; i <= M+1; i++){
Map[N+1][i] = ‘o‘;
Map[0][i] = ‘o‘;
}
for(int i = 0; i <= N+1; i++){
Map[i][0] = ‘o‘;
Map[i][M+1] = ‘o‘;
}
for(int i = 1; i <= N; i++){
getchar();
for(int j = 1; j <= M; j++){
scanf("%c",&Map[i][j]);
if(Map[i][j] == ‘*‘){
if((i+j)%2 == 0){
++n;
lis[i][j] = n;
if(Map[i-1][j] == ‘*‘){
G[n].push_back(lis[i-1][j]);
}
if(Map[i][j-1] == ‘*‘){
G[n].push_back(lis[i][j-1]);
}
}else{
++m;
lis[i][j] = m;
if(Map[i-1][j] == ‘*‘){
G[lis[i-1][j]].push_back(m);
}
if(Map[i][j-1] == ‘*‘){
G[lis[i][j-1]].push_back(m);
}
}
}
}
}
int res = MaxMatch(n,m);
printf("%d\n",n+m-res);
}
return 0;
}
/*
55
4 4
o***
oo*o
oooo
oooo
*/
POJ 3020——Antenna Placement——————【 最小路径覆盖、奇偶性建图】
原文：http://www.cnblogs.com/chengsheng/p/4955498.html