网络流/最大流/二分or贪心
题目大意：有n个队伍，两两之间有一场比赛，胜者得分+1，负者得分+0，问最多有几只队伍打败了所有得分比他高的队伍？
可以想到如果存在这样的“strong king”那么一定是胜场较多的队伍……（比他赢得多的队伍num少，而他总共赢得场数times足够多，至少得满足times>=num吧？）
那么我们可以二分/枚举k，表示胜场前k多的队伍是stong king。（这题范围小，只有10支队伍，如果队伍较多我们就需要二分了……）
最最丧心病狂的是！！！出题人TMD卡读入！！！居然在数字与数字之间会有多个空格！！！像我这样直接遇到空格就a[++n]=v,v=0;的就挂了！！！
妈蛋害我调了一晚上！
Source Code
Problem: User: sdfzyhy
Memory: 716K Time: 0MS
Language: G++ Result: Accepted Source Code //POJ 2699
#include<vector>
#include<cstdio>
#include<sstream>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,tot,ans,num,a[N];
char s1[N];
struct edge{int to,v;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int v){
E[++cnt]=(edge){y,v};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int v){
ins(x,y,v); ins(y,x,);
}
int s,t,d[N],Q[M];
bool mklevel(){
F(i,,t) d[i]=-;
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[t]!=-;
}
int dfs(int x,int a){
if (x==t) return a;
int flow=;
for(int i=head[x];i && flow<a;i=next[i])
if (E[i].v && d[E[i].to]==d[x]+){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()) ans+=dfs(s,INF);
}
void init(){
n=;
gets(s1);
int v=;
stringstream ss(s1);
while(ss >> v) a[++n]=v;
}
bool check(int k){
cnt=; F(i,s,t) head[i]=;
F(i,,n) add(s,i,a[i]);
int l=n;
F(i,,n) F(j,i+,n){
add(++l,t,);
if(i>=k && a[j]>a[i]) add(i,l,);
else add(i,l,),add(j,l,);
}
ans=;
Dinic();
return ans==m;
}
void solve(){
m=n*(n-)/;
s=; t=n+m+;
int l=,r=n,mid,as=;
/*
while(l<=r){
mid=l+r>>1;
// printf("l=%d r=%d mid=%d\n",l,r,mid);
if (check(mid)) as=mid,r=mid-1;
else l=mid+1;
}
二分 */
// D(i,n,1) if(!check(i)){as=i;break;} F(i,,n) if(check(i)){as=i-;break;}
printf("%d\n",n-as);
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("2699.in","r",stdin);
freopen("2699.out","w",stdout);
#endif
int T=getint();
while(T--){
G1.init();G1.solve();
}
return ;
}