神题目=神题解+神读入
题意：n个人比赛, 两两比，共n*(n-1), 赢得1分, n<=10(这给了我们枚举的暗示)，如果一个人打败了所有比自己分数高的人, 或者他本身就是分数最高的, 那么他就是StrongKing。可能有多个Strong King, 现在按非降的顺序给你每个人的得分(不难道想到容量把), 问Strong King最多能有几个
题解：二分图，左边是人，右边是比赛，源点到人连容量为score[i]的边，汇点到比赛连容量为1的边。然后枚举答案ans，由于分数越高的人成为strongking的可能性较大（我一开始没有意识到这点，还想用2^10的枚举），于是让后ans个人成为strongking，然后对这ans个人中的i，j，如果score[i]<score[j]则i向match[i][j]连容量为1的边。然后对剩余的比赛match[i][j],让i，j分别向点match[i][j]连容量为1的边。当maxflow==n*(n-1)/2时，则ans为解
贴代码（看读入...）:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=,maxm=,inf=0x7fffffff;
int n,m,a,b,c,s,t,tot=,maxflow,k[maxn],head[maxn],cur[maxn],h[maxn];
queue<int> q;
char ss[maxn];
struct node{
int go,next,v;
}e[maxm];
inline int read(){
int x=,f=;char ch=getchar();
while (ch>'' || ch<''){if (ch=='\n') return -;ch=getchar();}
while (ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void addedge(int x,int y,int v){
e[++tot]=(node){y,head[x],v};head[x]=tot;
e[++tot]=(node){x,head[y],};head[y]=tot;
}
bool bfs(){
for (int i=;i<=t;i++) h[i]=-;
q.push(s);h[s]=;
while (!q.empty()){
int x=q.front();q.pop();
for (int i=head[x];i;i=e[i].next){
if (e[i].v&&h[e[i].go]==-){
h[e[i].go]=h[x]+;
q.push(e[i].go);
}
}
}
return h[t]!=-;
}
int dfs(int x,int f){
if (x==t) return f;
int tmp,used=;
for (int i=cur[x];i;i=e[i].next){
if (e[i].v&&h[e[i].go]==h[x]+){
tmp=dfs(e[i].go,min(e[i].v,f-used));
e[i].v-=tmp;if (e[i].v) cur[x]=i;
e[i^].v+=tmp;used+=tmp;
if (used==f) return f;
}
}
if (!used) h[x]=-;
return used;
}
void dinic(){
maxflow=;
while (bfs()){
for (int i=;i<=t;i++) cur[i]=head[i];
maxflow+=dfs(s,inf);
}
}
int main(){
n=read();
while (n--){
m=;
//神读入
gets(ss);
int x=,l=strlen(ss);
for (int i=;i<l;i++){
if (ss[i]>='' && ss[i]<=''){
x=x*+ss[i]-'';
if (i==l- || ss[i+]==' ') k[++m]=x,x=;
}
} s=m+;t=;c=m*(m-)/;
for (int i=m;i;i--){
// cout<<"i:"<<i<<endl;
tot=;
memset(head,,sizeof(head));
for (int j=;j<=m;j++) addedge(s,j,k[j]);
for (int j=;j<m;j++)
for (int w=j+;w<=m;w++){
addedge(j*m+w,t,);
if (j<i || w<i || k[j]==k[w]) addedge(j,j*m+w,),addedge(w,j*m+w,);
}
for (int j=i;j<m;j++)
for (int w=j+;w<=m;w++) if (k[j]<k[w]) addedge(j,j*m+w,);
dinic();
// cout<<maxflow<<endl;
if (maxflow!=c){
printf("%d\n",m-i);
break;
}
if (i==) printf("%d\n",m);
}
}
return ;
}