【分析】
主要是有一个贪心的思想，就是如果有一种情况使其中k个人是能力者的话，那么总有一种情况使分数最高的k个人是能力者。（因为交换一下胜利的场就可以了）。所以可以枚举有k个人是能力者，规定后k个人就是能力者，建立约束图，跑最大流判满流即可。
如下图（证明上面那一个贪心）：
假设有一种情况使得有k个能力者，但不是后k个，证明有一种情况是后k个都是能力者。
上图，假设C是能力者但不是后k个，E不是能力者但是后k个。
因为C是能力者E不是，则在E的后面必有一个G（随便是什么），C赢了它，E没有赢他。
因为E的分数大于C，则在C之前必有一个A（随便是什么），C没有赢他，E赢了他。
那么我们交换一下胜负场，C、E分数都不变，然后E离能力者更近一步。
继续交换下去，后k个一定能成为能力者。
证毕。
于是建个图跑最大流。
差不多这样建图：
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1100
#define Maxm 100100
#define INF 0xfffffff char s[];
int a[Maxn],al,lg[Maxn];
int dis[Maxn],first[Maxn]; struct node
{
int x,y,f,o,next;
}t[Maxm];int len; int st,ed,sum,h=; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y,int f)
{
if(f==) return;
if(y==ed) sum+=f;
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} queue<int > q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
}
if(dis[ed]==-) return ;
return ;
} int ffind(int x,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
}
if(now==flow) break;
}
if(now==) dis[x]=-;
return now;
} bool max_flow()
{
int ans=;
while(bfs())
{
ans+=ffind(st,INF);
}
if(ans==sum) return ;
return ;
} bool check(int x)
{
len=;sum=;h=ed;
memset(first,,sizeof(first));
for(int i=al-x+;i<=al;i++)
{
if(a[i]<lg[i]) return ;
ins(i,ed,a[i]-lg[i]);
for(int j=i+;j<=al-lg[i];j++)
{
ins(st,++h,);
ins(h,i,);
ins(h,j,);
}
}
for(int i=;i<=al-x;i++) ins(i,ed,a[i]);
for(int i=;i<=al-x;i++)
for(int j=i+;j<=al;j++)
{
ins(st,++h,);
ins(h,i,);
ins(h,j,);
} if(max_flow()) return ; return ;
} int main()
{
int T;
scanf("%d",&T);getchar();
while(T--)
{
gets(s);
int l=strlen(s);
int now=;al=;
for(int i=;i<l;i++)
{
if((s[i]<=''||s[i]>='')&&(i>=&&s[i-]>=''&&s[i-]<=''))
{
a[++al]=now;
now=;
}
else if(s[i]>=''&&s[i]<='')now=now*+s[i]-'';
}
if(s[l-]>=''&&s[l-]<='') a[++al]=now;
for(int i=;i<=al;i++)
{
lg[i]=;
for(int j=i+;j<=al;j++) if(a[j]>a[i]) lg[i]++;
}
st=al+;ed=st+;h=ed;
int ans=;
for(int i=al;i>=;i--)
{
if(check(i)) {ans=i;break;}
}
printf("%d\n",ans);
}
return ;
}
[POJ2699]
2016-06-05 10:17:08