poj2699:http://poj.org/problem?id=2699
题意：n个人，进行n*(n-1)/2场比赛，赢一场则得到一分。如果一个人打败了所有比他分数高的对手，或者他就是分数最高的，那么他就是strong kind。现在给你每个人的得分，问你最多有多少个strong kind。
题解：自己没有思路，看了别人的题解，才勉强理解了。首先，肯定让得分高的成为strong king，因为概率比较大，然后就是怎建图了。假如，我们已经知道了，有m个strong kind，那么这m个人一定是后m个，所以，我们只要判断这m个是否满足条件就可以了，由于n很小，所以可以直接枚举ans。接下来就是建图，人作为一个点，与s建立一边，容量就是得分，然后比赛作为一种点，和t连接，容量是1，然后开始枚举ans，对于后ans个人来说，每个人i对于比他分高的选手j，都必须赢，所以对于i，j之间的比赛，i必须赢，所以i--mp[i][j](表示ij之间比赛的编号)建立一边，容量是1，然后对于剩余的比赛来说，i,j都可以赢，所以i,j都要建立一边到mp[i][j]容量是1，然后跑网络流，如果跑出的maxflow==n*(n-1)/2,说明这种方式是满足的，直接输出就可以了。这一题的读入不是很规范，数字之间不是严格的一个空格，可能有多个空格。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string>
#define INF 100000000
using namespace std;
const int N=;
const int M=;
struct Node{
int v;
int f;
int next;
}edge[M];
int n,m,u,v,tt,cnt,sx,ex;
int head[],pre[];
int g[],f[N],mp[][];//根据题目要求申请
void init(){
cnt=;
memset(head,-,sizeof(head));
memset(f,,sizeof(f));
}
void add(int u,int v,int w){
edge[cnt].v=v;
edge[cnt].f=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool BFS(){
memset(pre,,sizeof(pre));
pre[sx]=;
queue<int>Q;
Q.push(sx);
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=head[d];i!=-;i=edge[i].next ){
if(edge[i].f&&!pre[edge[i].v]){
pre[edge[i].v]=pre[d]+;
Q.push(edge[i].v);
}
}
}
return pre[ex]>;
}
int dinic(int flow,int ps){
int f=flow;
if(ps==ex)return f;
for(int i=head[ps];i!=-;i=edge[i].next){
if(edge[i].f&&pre[edge[i].v]==pre[ps]+){
int a=edge[i].f;
int t=dinic(min(a,flow),edge[i].v);
edge[i].f-=t;
edge[i^].f+=t;
flow-=t;
if(flow<=)break;
} }
if(f-flow<=)pre[ps]=-;
return f-flow;
}
int solve(){
int sum=;
while(BFS())
sum+=dinic(INF,sx);
return sum;
}
void build(int num){
init();
for(int i=;i<=n;i++)
add(,i,g[i]);
for(int i=;i<=tt;i++)
add(i+n,n+tt+,);
for(int i=n-num+;i<=n;i++)
for(int j=i+;j<=n;j++){
if(g[j]>g[i]){
f[mp[i][j]]=;
add(i,mp[i][j]+n,);
}
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
if(!f[mp[i][j]]){
add(i,mp[i][j]+n,);
add(j,mp[i][j]+n,);
}
}
}
string str;
int main() {
int T;
scanf("%d",&T);
getchar();
while(T--) {
n=;
getline(cin,str);
int len=str.length();
for(int i=;i<len;i++){
if(str[i]>=''&&str[i]<='')
g[++n]=str[i]-'';
}
tt=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
mp[i][j]=++tt;
sx=,ex=n+tt+;
int i;
for(i=n;i>;i--){
build(i);
if(solve()==tt)break;
}
printf("%d\n",i);
}
return ;
}