http://acm.hdu.edu.cn/showproblem.php?pid=3446
题意:一个棋盘，有个KING，有一些能走的点，每次只能走到没走过的地方，没路可走的输，求先手是否必胜。
思路:先去掉KING的位置，只考虑其他的，如果这样求出的匹配数和加上king的匹配数一样，说明KING这个位置没有在匹配中，因此后手必胜，否则先手必胜，为什么？
可以思考一下，匹配的路径是一条:匹配，不匹配，匹配。。。不匹配，匹配，因此如果KING在匹配中，那最后一步也能够是先手走的。
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> int dx[]={-1,-1,-1,1,1,1,0,0,2,-2,2,-2,2,-2,2,-2,1,-1,-1,1}; int dy[]={-1,1,0,0,1,-1,-1,1,2,2,-2,-2,1,-1,-1,1,2,-2,2,-2}; int match[250],G[250][250],inpath[250],q[250],head,tail,newbase; int inqueue[250],inblossom[250],base[250],father[250],n; int finish,start,R,C,kx,ky,c[250]; char s[25][25]; int read(){ int t=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f; } int lca(int u,int v){ memset(inpath,0,sizeof inpath); while (1){ u=base[u]; inpath[u]=1; if (!match[u]) break; u=father[match[u]]; } while (1){ v=base[v]; if (inpath[v]) break; v=father[match[v]]; } return v; } void reset(int u){ while (u!=newbase){ int v=match[u]; inblossom[base[v]]=inblossom[base[u]]=1; u=father[v]; if (base[u]!=newbase) father[u]=v; } } void blossomcontract(int u,int v){ newbase=lca(u,v); memset(inblossom,0,sizeof inblossom); reset(u); reset(v); if (base[u]!=newbase) father[u]=v; if (base[v]!=newbase) father[v]=u; for (int i=1;i<=n;i++) if (inblossom[base[i]]){ base[i]=newbase; if (!inqueue[i]) c[++tail]=i,inqueue[i]=1; } } void findaugmentingpath(){ memset(inqueue,0,sizeof inqueue); memset(father,0,sizeof father); for (int i=1;i<=n;i++) base[i]=i; head=1;tail=1;c[1]=start;inqueue[start]=1; finish=0; while (head<=tail){ int u=c[head++]; for (int v=1;v<=n;v++) if (G[u][v]&&base[u]!=base[v]&&match[v]!=u){ if (v==start||(match[v]>0)&&(father[match[v]]>0)){ blossomcontract(u,v); }else if (father[v]==0){ father[v]=u; if (match[v]){ c[++tail]=match[v];inqueue[match[v]]=1; }else{ finish=v; return; } } } } } void augmentpath(){ int u,v,w; u=finish; while (u>0){ v=father[u]; w=match[v]; match[u]=v; match[v]=u; u=w; } } int solve(){ int res=0; memset(match,0,sizeof match); for (int i=1;i<=n;i++) if (!match[i]){ start=i; findaugmentingpath(); if (finish) augmentpath(),res++; } return res; } int main(){ int T=read(),Tcase=0; while (T--){ printf("Case #%d: daizhenyang ",++Tcase); R=read();C=read(); memset(G,0,sizeof G); for (int i=1;i<=R;i++){ scanf("%s",s[i]+1); } for (int i=1;i<=R;i++) for (int j=1;j<=C;j++) if (s[i][j]!='#'){ for (int k=0;k<20;k++){ int x=i+dx[k],y=j+dy[k]; if (x>=1&&x<=R&&y>=1&&y<=C&&s[x][y]!='#'){ G[(i-1)*C+j][(x-1)*C+y]=1; G[(x-1)*C+y][(i-1)*C+j]=1; } } if (s[i][j]=='K') kx=i,ky=j; } n=R*C; int t1=solve(); int x=(kx-1)*C+ky; for (int i=1;i<=n;i++) if (G[x][i]) G[x][i]=G[i][x]=0; if (solve()==t1) puts("lose"); else puts("win"); } return 0; }