二分图匹配。
其实是很久以前做的题目了。今天被Usozki问了下这题怎么做，看了他的代码，感觉值得改进的地方不少……便自己着手重做了下这题，希望能讲清边表的写法。由于之前hackerhank出过一题很刁钻的匈牙利，觉得已经把这个算法弄得很透彻了（包括递归改非递归、每轮匈牙利时局部链表指针改全局、每次不重新memste标记数组等等），但这次重写这题还是用了很久。
这里用了一个题目的特点（可以染色成国际象棋棋盘那样的二分图），使得每个匹配的共算了两次；又或者其实可以每次仅从一种颜色的点出发，这样就只算一次匹配。
这是今天写的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<cstdio> #include<cstring> char s[40][11]; int h,w,bi,hd[400],d[40][10],b[400],f[400],el,si; struct E { int v,p; }e[1600]; inline void adde(int u,int v) { e[el].v=v; e[el].p=hd[u]; hd[u]=el++; e[el].v=u; e[el].p=hd[v]; hd[v]=el++; } int hun(int i) { int j,k,l; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].v; if(b[j]==bi) continue; b[j]=bi; if(f[j]==-1||hun(f[j])) { f[j]=i; return 1; } } return 0; } void init() { int i,j; si=el=0; memset(hd,-1,sizeof hd); memset(d,-1,sizeof d); for(i=0;i<h;i++) { scanf("%s",s[i]); for(j=0;j<w;j++) if(s[i][j]=='*') d[i][j]=si++; if(i) for(j=0;j<w;j++) if(d[i][j]!=-1&&d[i-1][j]!=-1) adde(d[i][j],d[i-1][j]); for(j=1;j<w;j++) if(d[i][j]!=-1&&d[i][j-1]!=-1) adde(d[i][j],d[i][j-1]); } memset(b,-1,sizeof b); memset(f,-1,sizeof f); } void solve() { int c=0; for(bi=0;bi<si;bi++) c+=hun(bi); printf("%d\n",si-c/2); } int main() { scanf("%*d"); while(~scanf("%d%d",&h,&w)) { init(); solve(); } return 0; } |
这里建图是先编号，再检查上方和左方是否存在点，然后加边的。代码里函数功能应该都区分得很明显了。这样写出来的边表，是做很多图论题时必须使用的数据结构（甚至其他类型题目里也经常用到）。无论是时间、空间，还是代码实现难度方面都是很好的。
另外也贴下以前写的，当时不会用边表，但是代码还算是比较齐整了：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<stdio.h> #include<string.h> int t,n,h,w,a[40][10],b[400],d[400][400],f[400]; char s[40][11]; int dfs(int i) { int j,k,l; for(j=0; j<n; j++) { if(!b[j]&&d[i][j]) { b[j]=1; if(f[j]==-1||dfs(f[j])) { f[j]=i; return 1; } } } return 0; } int main() { int i,j,k,l; scanf("%d",&t); while(t--) { memset(a,-1,sizeof(a)); memset(d,0,sizeof(d)); memset(f,-1,sizeof(f)); n=0; scanf("%d%d",&h,&w); for(i=0; i<h; i++) { scanf("%s",s[i]); for(j=0; j<w; j++) if(s[i][j]=='*') a[i][j]=n++; } for(i=0; i<h; i++) { for(j=i&1; j<w; j+=2) { if(a[i][j]>-1) { if(i>0&&a[i-1][j]>-1) d[a[i][j]][a[i-1][j]]=1; if(i<h-1&&a[i+1][j]>-1) d[a[i][j]][a[i+1][j]]=1; if(j>0&&a[i][j-1]>-1) d[a[i][j]][a[i][j-1]]=1; if(j<w-1&&a[i][j+1]>-1) d[a[i][j]][a[i][j+1]]=1; } } } for(i=j=0; i<n; i++) { memset(b,0,sizeof(b)); j+=dfs(i); } printf("%d\n",n-j); } return 0; } |