這題目，，，真是。。。誒?？恿撕镁谩?/span>

給一個有向圖。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 555500 using 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; }

轉載于:https://www.cnblogs.com/lochan/p/3854855.html

總結

以上是生活随笔為你收集整理的POJ2699_The Maximum Number of Strong Kings的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。