2分图
构图
两个集合是一样的,都是所有的*号
如果某两个*之间挨着,就连线
求最大匹配
可以轻易得出这个最大匹配把每个*都求了2遍
因此除以2,再加上未匹配的*,得解..
难点就是构图..
事实上匹配,网络流等的难点也就是构图
#include <iostream>
//#include <fstream>
using namespace std;
//ifstream fin("t3020.in");
struct node
{
int x,y;
};
const int MAXN=401;
node edge[MAXN];
bool connect[MAXN][MAXN];
bool hash[MAXN];
int v[MAXN];
int n;
int h,w;
int len;
bool find(int x)
{
for (int i=1;i<=len;i++)
{
if (!connect[x][i]) continue;
if (!hash[i])
{
hash[i]=true;
if (v[i]==0||find(v[i]))
{
v[i]=x;
return true;
}
}
}
return false;
}
int main()
{
cin>>n;
while(n--)
{
cin>>h>>w;
len=0;
for (int i=1;i<=h;i++)
for (int j=1;j<=w;j++)
{
char ch;
cin>>ch;
if ('*'==ch)
{
len++;
edge[len].x=i;
edge[len].y=j;
}
}
//init
memset(connect,0,sizeof(connect));
for (int i=1;i<=len;i++)
for (int j=1;j<=len;j++)
{
if (i==j) continue;
if (1==abs(edge[i].x-edge[j].x)+abs(edge[i].y-edge[j].y))
connect[i][j]=true;
}
//
memset(v,0,sizeof(v));
int answer=0,ans=0;
for (int i=1;i<=len;i++)
{
memset(hash,0,sizeof(hash));
if (find(i)) answer++;
else
ans++;
}
cout<<answer/2+ans<<endl;
// system("pause");
}
return 0;
}