HDU4185 Oil Skimming 二分图匹配 匈牙利算法 题目传送门 - HDU4185 题意概括 题解 代码
原文链接http://www.cnblogs.com/zhouzhendong/p/8231146.html
题意概括
每次恰好覆盖相邻的两个#，不能重复，求最大覆盖次数。（引用大佬的http://blog.****.net/u011721440/article/details/38144339）
题解
我们对于每两个相邻#的建边（来回两条）。
然后我们把格子黑白染色一下，发现黑点只会向白点连边，白点只会连向黑点连边，于是这个就是二分图了。
然后跑一跑匈牙利。
答案要除以2，因为你建了来回边。
注意，本题的#很少，不超过600个。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=1005;
int T,n,tn[N][N],g[N][N],cnt,match[N],vis[N];
char pl[N][N];
bool check(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=n&&tn[x][y];
}
bool Match(int x){
for (int i=1;i<=cnt;i++)
if (g[x][i]&&!vis[i]){
vis[i]=1;
if (match[i]==-1||Match(match[i])){
match[i]=x;
return 1;
}
}
return 0;
}
int hungary(){
int res=0;
memset(match,-1,sizeof match);
for (int i=1;i<=cnt;i++){
memset(vis,0,sizeof vis);
if (Match(i))
res++;
}
return res;
}
int main(){
scanf("%d",&T);
for (int Case=1;Case<=T;Case++){
scanf("%d",&n);
cnt=0;
memset(tn,0,sizeof tn);
for (int i=1;i<=n;i++){
scanf("%s",pl[i]+1);
for (int j=1;j<=n;j++)
if (pl[i][j]=='#')
tn[i][j]=++cnt;
}
memset(g,0,sizeof g);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
if (pl[i][j]!='#')
continue;
if (check(i,j-1))
g[tn[i][j]][tn[i][j-1]]=1;
if (check(i,j+1))
g[tn[i][j]][tn[i][j+1]]=1;
if (check(i-1,j))
g[tn[i][j]][tn[i-1][j]]=1;
if (check(i+1,j))
g[tn[i][j]][tn[i+1][j]]=1;
}
printf("Case %d: %d
",Case,hungary()/2);
}
return 0;
}