//最小边覆盖
//最小边覆盖=最大独立集=n-最大匹配
//这个是在原图是二分图上进行的
//由于此题为无向图
//最小边覆盖=最大独立集=n-最大匹配/2;
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 45*15;
int line[maxn][maxn];
int match[maxn];
int vis[maxn];
char str[maxn][maxn];
int N; int num = 0;
int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
int find(int start)
{
for(int i = 1;i <= N;i++)
{
if(!vis[i] && line[start][i])
{
vis[i] = 1;
if(match[i] == -1 || find(match[i]))
{
match[i] = start;
return 1;
}
}
}
return 0;
}
void Match()
{
memset(match , -1 ,sizeof(match));
int ans = 0;
for(int i = 1;i <= N ;i++)
{
memset(vis , 0,sizeof(vis));
if(find(i))
ans++;
}
printf("%d\n",num-ans/2);
}
int main()
{
// freopen("in.txt","r",stdin);
int T ;
scanf("%d" , &T);
while(T--)
{
int R,C;
memset(line, 0 ,sizeof(line));
scanf("%d%d", &R ,&C);
N = (R+1)*C;num = 0;
for(int i = 1;i <= R ;i++)
scanf("%s",&str[i][1]);
for(int i = 1;i <= R ;i++)
{
for(int j = 1;j <= C;j++)
{
if(str[i][j] == ‘*‘)
{
num++;
for(int k = 0 ;k < 4 ;k++)
if(str[i+dx[k]][j+dy[k]]==‘*‘)
line[(i)*C+j][(i+dx[k])*C+(j+dy[k])] = 1;
}
}
}
Match();
}
return 1;
}
poj 3020Antenna Placement 最小边覆盖
原文：http://blog.csdn.net/cq_pf/article/details/44523067
