<span>HDU1045 Fire Net（二分匹配）</span>
题意：
给出一张n*n的图，图中'X'表示墙,'.'表示空地,可以放点
同一条直线上只能有一个点，除非有墙隔开，问在给出的图中
最多能放置多少个点
思路：
4*4的图。。暴搜完全就可以了，不过是二分匹配专题就学了一发
把原图按行按列缩点，一行一列相邻的区域只能放一个
然后用行点和列点进行匹配，输出最大匹配
/* *********************************************** Author :devil Created Time :2016/5/5 10:31:47 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; char s[5][5]; int l[5][5],r[5][5],ll,rl,link[8]; bool mp[8][8],vis[8]; int dfs(int u) { for(int i=0; i<ll; i++) { if(mp[u][i]&&!vis[i]) { vis[i]=1; if(link[i]==-1||dfs(link[i])) { link[i]=u; return 1; } } } return 0; } int main() { //freopen("in.txt","r",stdin); int n; while(~scanf("%d",&n)&&n) { for(int i=0; i<n; i++) scanf("%s",s[i]); ll=rl=0; memset(l,-1,sizeof(l)); memset(r,-1,sizeof(r)); memset(mp,0,sizeof(mp)); memset(link,-1,sizeof(link)); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(s[i][j]=='.'&&r[i][j]==-1) { for(int k=j; k<n&&s[i][k]=='.'; k++) r[i][k]=rl; rl++; } if(s[j][i]=='.'&&l[j][i]==-1) { for(int k=j; k<n&&s[k][i]=='.'; k++) l[k][i]=ll; ll++; } } } for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(s[i][j]=='.') mp[r[i][j]][l[i][j]]=1; int ans=0; for(int i=0; i<rl; i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d\n",ans); } return 0; }
