POJ2226

题目大意：

又是网格图

一个有(.)和(*)构成的网格图，要求用(1*x)的木板覆盖所有(*)且不覆盖到(.)，求需要的最少木板

(n,mle 100)

把每个行和列联通块看作一个点，然后就是二分图最小点覆盖

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
		if(ch=='-') f=0,ch=getchar();
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return f?x:-x;
	}
	const int N=1010;
	int n,m,ret;
	int id[N][N],tot;
	int idx[N][N],idy[N][N],totx,toty;
	char s[N][N];
	bool vis[N*N];
	int f[N*N];
	int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
	int head[N*N],cnt;
	struct point
	{
		int nxt,to;
		point(){}
		point(const int &nxt,const int &to):nxt(nxt),to(to){}
	}a[N*N];
	inline void link(int x,int y)
	{
		a[++cnt]=point(head[x],y);head[x]=cnt;
		a[++cnt]=point(head[y],x);head[y]=cnt;
	}
	inline void dfs1(int x,int y)
	{
		idx[x][y]=totx;
		if(y>1&&s[x][y-1]=='*'&&!idx[x][y-1]) dfs1(x,y-1);
		if(y<m&&s[x][y+1]=='*'&&!idx[x][y+1]) dfs1(x,y+1);
	}
	inline void dfs2(int x,int y)
	{
		idy[x][y]=toty;
		if(x>1&&s[x-1][y]=='*'&&!idy[x-1][y]) dfs2(x-1,y);
		if(x<n&&s[x+1][y]=='*'&&!idy[x+1][y]) dfs2(x+1,y);
	}
	inline bool find(int x)
	{
		for(int i=head[x];i;i=a[i].nxt)
		{
			int t=a[i].to;
			if(vis[t]) continue;
			vis[t]=1;
			if(!f[t]||find(f[t]))
			{
				f[t]=x;
				return 1;
			}
		}
		return 0;
	}
	inline void main()
	{
		while(scanf("%lld%lld",&n,&m)==2)
		{
			memset(head,0,sizeof(head));
			memset(f,0,sizeof(f));
			memset(idx,0,sizeof(idx));
			memset(idy,0,sizeof(idy));
			cnt=ret=tot=totx=toty=0;
			for(int i=1;i<=n;++i)
			{
				scanf("%s",s[i]+1);
				for(int j=1;j<=m;++j)
				{
					id[i][j]=++tot;
				}
			}
			for(int i=1;i<=n;++i)
			{
				for(int j=1;j<=m;++j)
				{	
					if(s[i][j]=='.') continue;
					if(!idx[i][j]) ++totx,dfs1(i,j);
					if(!idy[i][j]) ++toty,dfs2(i,j);
				}
			}
			for(int i=1;i<=n;++i)
			{
				for(int j=1;j<=m;++j)
				{
					if(s[i][j]=='.') continue;
					link(idx[i][j],idy[i][j]+totx);
				}
			}
			for(int i=1;i<=totx;++i)
			{
				memset(vis,0,sizeof(vis));
				if(find(i)) ++ret;
			}
			printf("%lld
",ret);
		}
	}
}
signed main()
{
	red::main();
return 0;
}