讲的很好的资料：
点击打开链接
#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; const int maxn=30; struct node { int from,to,cap,flow; }; struct dinic { int n,m,s,t; vector e; vector g[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { e.clear(); for(int i=0;i<=n+2;i++) g[i].clear(); } void addedge(int a,int b,int c,int d) { e.push_back((node){a,b,c,0}); e.push_back((node){b,a,d,0}); m=e.size(); g[a].push_back(m-2); g[b].push_back(m-1); } bool bfs() { memset(vis,0,sizeof vis); queue q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=0;i ee.flow) { vis[ee.to]=1; d[ee.to]=d[x]+1; q.push(ee.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0) return a; int flow=0,f; for(int& i=cur[x];i 0) { ee.flow+=f; e[g[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int maxflow(int s,int t) { this->s=s; this->t=t; int flow=0; while(bfs()) { memset(cur,0,sizeof cur); flow+=dfs(s,inf); } return flow; } }; dinic solve; int r[30],vis[30],in[30],out[30]; int root(int a) { if(r[a]==-1) return a; return r[a]=root(r[a]); } void merge(int a,int b) { int ra=root(a); int rb=root(b); if(ra!=rb) r[ra]=rb; } int main() { char s[22]; int T,a,i,n,u,v,j,d,tmp,cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); solve.init(26); memset(in,0,sizeof in); memset(out,0,sizeof out); memset(vis,0,sizeof vis); memset(r,-1,sizeof r); for(i=0;i 0&&d%2) v=i,tmp++; if(tmp>2) flag=0; } if(!flag) { printf("Case %d: Poor boy!\n",cas++); continue; } if(tmp==2) solve.addedge(u,v,1,0); int sum=0; for(i=0;i<26;i++) { d=in[i]-out[i]; if(d<0) solve.addedge(26,i,-d/2,0); else if(d>0) { solve.addedge(i,27,d/2,0); sum+=d/2; } } tmp=solve.maxflow(26,27); // printf("sum:%d flow:%d\n",sum,tmp); if(tmp!=sum) printf("Case %d: Poor boy!\n",cas++); else printf("Case %d: Well done!\n",cas++); } return 0; }