[并查集+混合图欧拉回路+网络流]hdoj 3472：HS BDC
大致题意：
? ? 给出你n个单词，如果一个单词的尾部和另一个单词的头部相同那么这两个单词就能连在一起(比如‘abc’和‘cde’就能够连成abc-cde)，如果这个单词后面的数字是1，则代表这个单词的逆序也是一个单词，可以翻转过来。求所有单词能不能连成一长串。
?
大致思路：
? ? 转化为混合图的欧拉回路，把字母当作节点。注意要用并查集来检测图是否连通。
?
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const int inf=1<<30;const int nMax=2000;const int mMax=100000;class node{ public: int c,u,v,next;};node edge[mMax];int ne, head[nMax];int cur[nMax], ps[nMax], dep[nMax];void addedge(int u, int v,int w){ ////dinic邻接表加边 // cout<<u<<" add "<<v<<endl; edge[ne].u = u; edge[ne].v = v; edge[ne].c = w; edge[ne].next = head[u]; head[u] = ne ++; edge[ne].u = v; edge[ne].v = u; edge[ne].c = 0; edge[ne].next = head[v]; head[v] = ne ++;}int dinic(int s, int t){ // dinic int tr, res = 0; int i, j, k, f, r, top; while(1){ memset(dep, -1, sizeof(dep)); for(f = dep[ps[0]=s] = 0, r = 1; f != r;) for(i = ps[f ++], j = head[i]; j; j = edge[j].next) if(edge[j].c && dep[k=edge[j].v] == -1){ dep[k] = dep[i] + 1; ps[r ++] = k; if(k == t){ f = r; break; } } if(dep[t] == -1) break; memcpy(cur, head, sizeof(cur)); i = s, top = 0; while(1){ if(i == t){ for(tr =inf, k = 0; k < top; k ++) if(edge[ps[k]].c < tr) tr = edge[ps[f=k]].c; for(k = 0; k < top; k ++){ edge[ps[k]].c -= tr; edge[ps[k]^1].c += tr; } i = edge[ps[top=f]].u; res += tr; } for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){ if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break; } if(cur[i]){ ps[top ++] = cur[i]; i = edge[cur[i]].v; } else{ if(top == 0) break; dep[i] = -1; i = edge[ps[-- top]].u; } } } return res;}char str[30];int in[nMax];int out[nMax];bool vis[nMax];int p[nMax],r[nMax];int find(int a){ if(p[a]!=a){ p[a]=find(p[a]); } return p[a];}void unionset(int i,int j){ i=find(i); j=find(j); if(i!=j){ if(r[i]>r[j]){ p[j]=i; } else{ p[i]=j; if(r[i]==r[j]){ r[i]++; } } }}int main(){ int i,j,k,cas,a,b,n,f,len,flag,s,t,sum; scanf("%d",&cas); for(int ii=1;ii<=cas;ii++){ s=27,t=28; ne=2; flag=1; memset(head,0,sizeof(head)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); for(i=0;i<100;i++)p[i]=i,r[i]=0; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%s%d",str,&f); len=strlen(str); in[str[len-1]-'a']++; out[str[0]-'a']++; vis[str[0]-'a']=vis[str[len-1]-'a']=1; unionset(str[len-1]-'a',str[0]-'a'); if(f==1){ addedge(str[0]-'a',str[len-1]-'a',1); } } printf("Case %d:",ii); for(i=0;i<26;i++){ if(vis[i]){ for(j=i+1;j<26;j++){ if(vis[j]){ if(find(i)!=find(j)){ flag=0; break; } } } break; } } int v1=-1,v2=-1,tmp=0; for(i=0;i<26;i++){ if(!vis[i])continue; if((in[i]-out[i])%2==1){ v1=i; tmp++; } if((in[i]-out[i])%2==-1){ v2=i; tmp++; } } if(tmp==0||(tmp==2&&v1!=-1&&v2!=-1)){ if(tmp==2){ addedge(v1,v2,1); in[v2]++; out[v1]++; } } else{ flag=0; } if(!flag){ printf(" Poor boy!\n"); continue; } sum=0; for(i=0;i<26;i++){ if(!vis[i])continue; tmp=(out[i]-in[i])/2; if(tmp<0){ addedge(i,t,-tmp); } else if(tmp>0){ sum+=tmp; addedge(s,i,tmp); } } if(dinic(s,t)!=sum){ printf(" Poor boy!\n"); } else{ printf(" Well done!\n"); } } return 0;}?