这题目，，，真是。。。诶。坑了好久。
给一个有向图。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>>;
int next[maxm],to[maxm],c[maxm],first[maxn],edge;
int d[maxn],tag[maxn],f[maxn][maxn],TAG=;
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=,m=,maxscore=;
int L=strlen(S);
for (int i=; i<L; i++)
{
if (S[i]>='' && S[i]<='')
{
m=m*+S[i]-'';
if (i==L- || S[i+]<'' || S[i+]>'')
a[++n]=m,m=,maxscore=max(maxscore,a[n]);
}
}
for (int i=; i<n; i++)
for (int j=i+; j<=n; j++)
f[i][j]=f[j][i]=++m;
//cout<<n<<' '<<m<<endl;
s=,t=n+m+,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]=,next[edge]=first[V],first[V]=edge;
} bool bfs()
{
Q[bot=top=]=t,d[t]=,tag[t]=++TAG,can[t]=false;
while (bot<=top)
{
int cur=Q[bot++];
for (int i=first[cur]; i!=-; i=next[i])
if (c[i^]> && tag[to[i]]!=TAG)
{
tag[to[i]]=TAG;
d[to[i]]=d[cur]+;
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!=-; i=next[i])
if (c[i]> && tag[to[i]]==TAG && d[to[i]]==d[cur]- && !can[to[i]])
{
k=dfs(to[i],min(c[i],num));
if (k) num-=k,c[i]-=k,c[i^]+=k;
if (num==) break;
}
if (num) can[cur]=true;
return tmp-num;
} bool check(int x)
{
edge=-;
for (int i=s; i<=t; i++) first[i]=-;
for (int i=; i<=n; i++) addedge(s,i,a[i]);
for (int i=; i<x; i++)
for (int j=i+; j<=n; j++)
addedge(i,f[i][j]+n,),addedge(j,f[i][j]+n,);
for (int i=x; i<n; i++)
for (int j=i+; j<=n; j++)
{
addedge(i,f[i][j]+n,);
if (a[i]==maxscore) addedge(j,f[i][j]+n,);
}
for (int i=n+; i<=n+sum; i++) addedge(i,t,);
for (ans=; bfs(); ) ans+=dfs(s,inf);
return ans>=sum;
} int main()
{
scanf("%d",&T);
getchar();
while (T--)
{
_input();
for (int i=; i<=n; i++)
if (check(i))
{
printf("%d\n",n-i+);
break;
}
}
return ;
}