poj3020——Antenna Placement

这道题，不分左右的x,y点，直接匹配。将最终的匹配数ans除以2即可。而答案的话，应该是result=cnt(总的点数)-2*(ans/2)+ans/2。

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
#define H 45
#define maxn 450
string date[H];
int dir[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int map[H][H];
int h,w;
class node
{
public:
	int to;
	int next;
};
node g[maxn*100];
int head[maxn],cnt,len;
bool vis[maxn];
int my[maxn];
bool dfs(int v)
{
	int i;
	for(i=head[v];i;i=g[i].next )
	{
		int u=g[i].to ;
		if(vis[u])
		{
			vis[u]=false ;
			if(my[u]==-1||dfs(my[u]))
			{
				my[u]=v;return true;
			}
		}
	}
	return false;
}
void solve()
{
	int i,j,ans=0;
	for(i=1;i<=cnt;i++)
		my[i]=-1; 
	for(i=1;i<=cnt;i++)
	{
		memset(vis,true,sizeof(vis));
		if(dfs(i)) ans++;
	}
	ans/=2;
	int result=cnt-ans;
	cout<<result<<endl;
}
int main()
{
	int t,i,j;
	cin>>t;
	while(t--)
	{
		cin>>h>>w;
		memset(head,0,sizeof(head));
		for(i=0;i<h;i++)
			cin>>date[i];
		cnt=0;
		for(i=0;i<h;i++)
		{
			for(j=0;j<w;j++)
				if(date[i].at (j)=='*')
					map[i][j]=++cnt;
		}
		len=0;
		for(i=0;i<h;i++)
			for(j=0;j<w;j++)
				if(date[i].at (j)=='*')
				{
					for(int k=0;k<4;k++)
					{
						int tempx=i+dir[k][0];
						int tempy=j+dir[k][1];
						if(tempx>=0&&tempx<h&&tempy>=0&&tempy<w&&date[tempx].at (tempy)=='*')
						{
							g[++len].to =map[tempx][tempy];
							g[len].next =head[map[i][j]];
							head[map[i][j]]=len;
						}
					}
				}
		solve();
	}
	return 0;
}