题目：http://poj.org/problem?id=2584
像模板一样的简单题。继续使用 & 的当前弧优化和神奇的构造函数。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int n,head[30],dfn[30],cur[30],l,r,mxflow,xnt,x,t; const int INF=30; char tmp[15],tm1,tm2; struct Edge{ int next,to,cap; Edge(int a=0,int b=0,int c=0):next(a),to(b),cap(c) {} }edge[255]; queue<int> q; int num(char c) { if(c=='S')return 1+n;if(c=='L')return 3+n; if(c=='M')return 2+n;if(c=='X')return 4+n;if(c=='T')return 5+n; } bool bfs() { memset(dfn,0,sizeof dfn); while(!q.empty())q.pop(); dfn[0]=1; q.push(0); while(!q.empty()) { int k=q.front();q.pop(); for(int i=head[k],v;i;i=edge[i].next) if(!dfn[v=edge[i].to]&&edge[i].cap) { dfn[v]=dfn[k]+1; q.push(v); if(v==t)break; } } return dfn[t]; } int dfs(int k,int flow) { if(k==t)return flow; int used=0; for(int& i=cur[k],v;i;i=edge[i].next) if(dfn[v=edge[i].to]==dfn[k]+1&&edge[i].cap) { int tmp=dfs(v,min(flow-used,edge[i].cap)); if(!tmp)dfn[v]=0; used+=tmp; edge[i].cap-=tmp; edge[i^1].cap+=tmp; if(used==flow)return used; } return used; } int main() { while(1) { cin>>tmp; if(tmp[0]=='E')return 0; scanf("%d ",&n); memset(head,0,sizeof head); t=n+6;mxflow=0;xnt=1; for(int i=1;i<=n;i++) { edge[++xnt]=Edge(head[0],i,1);head[0]=xnt; edge[++xnt]=Edge(head[i],0,0);head[i]=xnt; scanf("%c%c ",&tm1,&tm2); l=num(tm1);r=num(tm2); for(int j=l;j<=r;j++) { edge[++xnt]=Edge(head[i],j,1);head[i]=xnt; edge[++xnt]=Edge(head[j],i,0);head[j]=xnt; } } for(int i=1+n;i<=5+n;i++) { scanf("%d",&x); edge[++xnt]=Edge(head[i],t,x);head[i]=xnt; edge[++xnt]=Edge(head[t],i,0);head[t]=xnt; } cin>>tmp; while(bfs()) { memcpy(cur,head,sizeof head); mxflow+=dfs(0,INF); } if(mxflow==n) printf("T-shirts rock! "); else printf("I'd rather not wear a shirt anyway... "); } }