首页 > 代码库 > POJ2699_The Maximum Number of Strong Kings
POJ2699_The Maximum Number of Strong Kings
这题目，，，真是。。。诶。坑了好久。
给一个有向图。U->V表示U可以打败V并得一分。
如果一个人的得分最高，或者他打败所有比自己得分高的人，那么此人就是king。
现在给出每个人的得分，求最多可能有多少个king同时存在。
可以证明，如果有k个人是king，那么至少有一种分配方案使得这k个king都是分数最高的那k个人。（证明略，想想就知道了）
于是我们可以开始枚举从i个人开始，后面的都是king。
除了源点和汇点以外，还有两种点，一种表示人(n)，一种表示比赛(n*(n/2)/2)。
如果一个人可以从一场比赛中得分，那么从人向该比赛连接一条流量为1的边。
对于当前枚举的第k个人，前面的的都不是king，那么两个人都可以连接到与该人相关的比赛，对于k以后的人，与自己编号大的人去比赛，只能是k本身获胜，这样网络流的模型就出来了。
我们从小到大枚举第一个king的位置，建图后判断能否满流即可。
此题是好题，只是。。。。这个输入就不敢恭维了。各种空格什么乱七八糟的奇怪的输入格式，一开始输入一个人数n会死哦？还有提示一个坑，如果有几个人的分数相同，那么即使他是在枚举位置的后面，他也可以输给与自己分数相同的人，特别注意了。
召唤代码君：
#include <iostream>#include <cstring>#include <cstdio>#define maxn 2550#define maxm 555500using namespace std;const int inf=~0U>>2;int next[maxm],to[maxm],c[maxm],first[maxn],edge;int d[maxn],tag[maxn],f[maxn][maxn],TAG=520;int Q[maxm],bot,top;bool can[maxn];int a[maxn],n,m,sum,ans,s,t,T,maxscore;char S[maxm];void _input(){ gets(S); n=0,m=0,maxscore=0; int L=strlen(S); for (int i=0; i<L; i++) { if (S[i]>=‘0‘ && S[i]<=‘9‘) { m=m*10+S[i]-‘0‘; if (i==L-1 || S[i+1]<‘0‘ || S[i+1]>‘9‘) a[++n]=m,m=0,maxscore=max(maxscore,a[n]); } } for (int i=1; i<n; i++) for (int j=i+1; j<=n; j++) f[i][j]=f[j][i]=++m; //cout<<n<<‘ ‘<<m<<endl; s=0,t=n+m+1,sum=m;}void addedge(int U,int V,int W){ //cout<<" A edge : "<<U<<" -> "<<V<<" :: "<<W<<endl; edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){ Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,can[t]=false; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1]>0 && tag[to[i]]!=TAG) { tag[to[i]]=TAG; d[to[i]]=d[cur]+1; can[to[i]]=false; Q[++top]=to[i]; if (to[i]==s) return true; } } return false;}int dfs(int cur,int num){ if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i]>0 && tag[to[i]]==TAG && d[to[i]]==d[cur]-1 && !can[to[i]]) { k=dfs(to[i],min(c[i],num)); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (num==0) break; } if (num) can[cur]=true; return tmp-num;}bool check(int x){ edge=-1; for (int i=s; i<=t; i++) first[i]=-1; for (int i=1; i<=n; i++) addedge(s,i,a[i]); for (int i=1; i<x; i++) for (int j=i+1; j<=n; j++) addedge(i,f[i][j]+n,1),addedge(j,f[i][j]+n,1); for (int i=x; i<n; i++) for (int j=i+1; j<=n; j++) { addedge(i,f[i][j]+n,1); if (a[i]==maxscore) addedge(j,f[i][j]+n,1); } for (int i=n+1; i<=n+sum; i++) addedge(i,t,1); for (ans=0; bfs(); ) ans+=dfs(s,inf); return ans>=sum;}int main(){ scanf("%d",&T); getchar(); while (T--) { _input(); for (int i=1; i<=n; i++) if (check(i)) { printf("%d\n",n-i+1); break; } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。