学步园

很巧妙的构图题，要把比赛顶点作为一个点，如果A B的胜负关系不能确定，他们各自向他们对应的比赛顶点连一条容量为1的边，否则，只要将必胜方与对应比赛连一条容量为1的边，每场比赛与汇点连一条容量为1的边，这样，表示出了一场比赛2选1的特点

源点与每个选手连一条容量为该选手得分的边

然后枚举k个Strong Kings，他们肯定是得分最高的那k个，如果A是Strong King，且B>A，若B的得分比A高，则A一定胜B

如果满流，说明可以存在k个Strong Kings

代码：

 #include<iostream><br /> #include<string><br /> using namespace std;<br /> #define inf 9999999<br /> #define MAX 105<br /> #define min(x,y) (x)<(y)?(x):(y)<br /> int score[15],cap[MAX][MAX],f[MAX][MAX];<br /> int pre[MAX],q[MAX],rc[MAX];<br /> int s,t,max_flow;<br /> void build(int start,int num)<br /> {<br /> int i,j,cnt=num;<br /> memset(cap,0,sizeof(cap));<br /> memset(f,0,sizeof(f));<br /> for(i=1;i<=num;i++)<br /> cap[s][i]=score[i];<br /> for(i=1;i<=num;i++)<br /> {<br /> for(j=i+1;j<=num;j++)<br /> {<br /> cnt++;<br /> if(i>=start&&score[j]>score[i])//i是Strong King，且j的得分比i高，i必胜<br /> {<br /> cap[i][cnt]=1;<br /> }<br /> else//i,j胜负未知<br /> {<br /> cap[i][cnt]=1;<br /> cap[j][cnt]=1;<br /> }<br /> cap[cnt][t]=1;<br /> }<br /> }<br /> }<br /> bool bfs()<br /> {<br /> int i,j,head=0,tail=1;<br /> memset(rc,0,sizeof(rc));<br /> pre[s]=-1;<br /> rc[s]=inf;<br /> q[tail]=s;<br /> while(head<tail)<br /> {<br /> i=q[++head];<br /> for(j=0;j<=t;j++)<br /> {<br /> if(cap[i][j]>f[i][j]&&!rc[j])<br /> {<br /> rc[j]=min(rc[i],cap[i][j]-f[i][j]);<br /> pre[j]=i;<br /> q[++tail]=j;<br /> if(j==t)<br /> return true;<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> void update()<br /> {<br /> for(int i=t;i!=s;i=pre[i])<br /> {<br /> f[pre[i]][i]+=rc[t];<br /> f[i][pre[i]]=-f[pre[i]][i];<br /> }<br /> max_flow+=rc[t];<br /> }<br /> void EK()<br /> {<br /> while(bfs())<br /> update();<br /> }<br /> int main()<br /> {<br /> int test,i,j,ans,n,l;<br /> char st[300];<br /> cin>>test;<br /> getchar();<br /> while(test--)<br /> {<br /> gets(st);<br /> l=strlen(st);<br /> j=0;<br /> for(i=0;i<l;i++)<br /> {<br /> if(st[i]<='9'&&st[i]>='0')<br /> score[++j]=st[i]-'0';<br /> }<br /> ans=0;<br /> n=j*(j-1)/2;<br /> s=0;<br /> t=j+n+1;<br /> for(i=j;i>=1;i--)<br /> {<br /> build(i,j);<br /> max_flow=0;<br /> EK();<br /> if(max_flow==n)<br /> {<br /> ans=j-i+1;<br /> }<br /> }<br /> printf("%d/n",ans);<br /> }<br /> system("pause");<br /> return 0;<br /> }<br />