题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3316
题意：棋盘上有n个棋子，2个人轮流拿棋子，第一步可以随意拿棋子，之后只能在上一步棋子曼哈顿距离L内拿棋子，不能拿棋子则输，问后手者能否赢得比赛。
思路：根据曼哈顿距离可以连接点，形成一个n个联通块的图，后手要赢，必须先手拿走的棋之后 有相连的棋（匹配的棋）。所以只要每个连通块的棋都是完美匹配的，后手拿先手匹配的棋，一定能赢，即只要整个图是完美匹配就行，这样每个联通块一定是完美匹配。
这里用到的一般图匹配的模板：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=250; bool g[maxn][maxn],inque[maxn],inpath[maxn]; bool inhua[maxn]; int st,ed,newbase,ans,n; int base[maxn],pre[maxn],match[maxn]; int head,tail,que[maxn]; void create() { int u,v; memset(g,0,sizeof(g)); scanf("%d",&n); while(scanf("%d%d",&u,&v)==2) { g[u][v]=g[v][u]=1; } } void Push(int u) { que[tail]=u; tail++; inque[u]=1; } int Pop() { int res=que[head]; head++; return res; } int lca(int u,int v)//寻找公共花祖先 { memset(inpath,0,sizeof(inpath)); while(1) { u=base[u]; inpath[u]=1; if(u==st) break; u=pre[match[u]]; } while(1) { v=base[v]; if(inpath[v]) break; v=pre[match[v]]; } return v; } void reset(int u)//缩环 { int v; while(base[u]!=newbase) { v=match[u]; inhua[base[u]]=inhua[base[v]]=1; u=pre[v]; if(base[u]!=newbase) pre[u]=v; } } void contract(int u,int v)// { newbase=lca(u,v); memset(inhua,0,sizeof(inhua)); reset(u); reset(v); if(base[u]!=newbase) pre[u]=v; if(base[v]!=newbase) pre[v]=u; for(int i=1;i<=n;i++) { if(inhua[base[i]]){ base[i]=newbase; if(!inque[i]) Push(i); } } } void findaug() { memset(inque,0,sizeof(inque)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++)//并查集 base[i]=i; head=tail=1; Push(st); ed=0; while(head<tail) { int u=Pop(); for(int v=1;v<=n;v++) { if(g[u][v]&&(base[u]!=base[v])&&match[u]!=v) { if(v==st||(match[v]>0)&&pre[match[v]]>0)//成环 contract(u,v); else if(pre[v]==0) { pre[v]=u; if(match[v]>0) Push(match[v]); else//找到增广路 { ed=v; return ; } } } } } } void aug() { int u,v,w; u=ed; while(u>0) { v=pre[u]; w=match[v]; match[v]=u; match[u]=v; u=w; } } void edmonds()//匹配 { memset(match,0,sizeof(match)); for(int u=1;u<=n;u++) { if(match[u]==0) { st=u; findaug();//以st开始寻找增广路 if(ed>0) aug();//找到增广路 重新染色，反向 } } } void print() { ans=0; for(int u=1;u<=n;u++) if(match[u]>0) ans++; printf("%d ",ans); for(int u=1;u<=n;u++) if(u<match[u]) printf("%d %d ",u,match[u]); } int main() { create(); edmonds(); print(); return 0; }
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=400; bool g[maxn][maxn],inque[maxn],inpath[maxn]; bool inhua[maxn]; int st,ed,newbase,ans,n; int base[maxn],pre[maxn],match[maxn]; int head,tail,que[maxn],a[maxn],b[maxn]; int dis(int a1,int b1,int a2,int b2) { return abs(a1-a2)+abs(b1-b2); } void Push(int u) { que[tail]=u; tail++; inque[u]=1; } int Pop() { int res=que[head]; head++; return res; } int lca(int u,int v)//寻找公共花祖先 { memset(inpath,0,sizeof(inpath)); while(1) { u=base[u]; inpath[u]=1; if(u==st) break; u=pre[match[u]]; } while(1) { v=base[v]; if(inpath[v]) break; v=pre[match[v]]; } return v; } void reset(int u)//缩环 { int v; while(base[u]!=newbase) { v=match[u]; inhua[base[u]]=inhua[base[v]]=1; u=pre[v]; if(base[u]!=newbase) pre[u]=v; } } void contract(int u,int v)// { newbase=lca(u,v); memset(inhua,0,sizeof(inhua)); reset(u); reset(v); if(base[u]!=newbase) pre[u]=v; if(base[v]!=newbase) pre[v]=u; for(int i=1;i<=n;i++) { if(inhua[base[i]]){ base[i]=newbase; if(!inque[i]) Push(i); } } } void findaug() { memset(inque,0,sizeof(inque)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++)//并查集 base[i]=i; head=tail=1; Push(st); ed=0; while(head<tail) { int u=Pop(); for(int v=1;v<=n;v++) { if(g[u][v]&&(base[u]!=base[v])&&match[u]!=v) { if(v==st||(match[v]>0)&&pre[match[v]]>0)//成环 contract(u,v); else if(pre[v]==0) { pre[v]=u; if(match[v]>0) Push(match[v]); else//找到增广路 { ed=v; return ; } } } } } } void aug() { int u,v,w; u=ed; while(u>0) { v=pre[u]; w=match[v]; match[v]=u; match[u]=v; u=w; } } void edmonds()//匹配 { memset(match,0,sizeof(match)); for(int u=1;u<=n;u++) { if(match[u]==0) { st=u; findaug();//以st开始寻找增广路 if(ed>0) aug();//找到增广路 重新染色，反向 } } } void print() { ans=0; for(int u=1;u<=n;u++) if(match[u]>0) ans++; if(ans==n) printf("YES "); else printf("NO "); } int main() { int l; while(scanf("%d",&n)!=EOF) { ans=0; memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); scanf("%d",&l); for(int i=1;i<=n;i++)//建图 { for(int j=i+1;j<=n;j++) { if(dis(a[i],b[i],a[j],b[j])<=l) g[i][j]=g[j][i]=1; } } edmonds();//匹配 for(int i=1;i<=n;i++) if(match[i]!=0) ans++; if(ans==n) printf("YES "); else printf("NO "); } return 0; }