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;
}