题目链接
(Describe)
一场联赛可以表示成一个完全图，点表示参赛选手，任意两点u, v之间有且仅有一条有向边((u, v))或((v, u))，表示(u)打败(v)或(v)打败(u)。一个选手的得分等于被他打败的选手总数。一个选手被称为(“strong king”)当且仅当他打败了所有比他分高的选手。分数最高的选手也是(“strong king”)。现在给出某场联赛所有选手的得分序列，由低到高，问合理安排每场比赛的结果后最多能有几个(“strong king”)已知选手总数不超过10个。
(Solution)
我们观察发现选手人数不超过(10)个,则说明(“strong king”)不超过10个,所以我们可以枚举(“strong king”)的个数,其实二分也可以的,将这些人的个数设为k
那么这些(“strong king”)的分数该如何确定呢?
引用一个结论:
对于一个分数序列，如果最多有(k)个(“strong king”)，那么必然存在一种比赛情况，就是分数最大的(k)个人是(“strong king”)
证明:
假设序列是这个模样，(1....i.....j.....k......n)
假设只有(i,k)是(“strong king”),而j不是. 假设(j)输给了(j+1)至(n)区间中的(x)个人，那么显然(i)是赢了这(x)个人的，我们现在想把(j)变为(“strong king”). 那么就让把(j)输了的这些场全变成赢，此时(j)分值增加了(x)，就将(j)与(i)之前的人们的比赛多输(x)场，这样(j)的分数守恒了，但是(j)一赢之后，原本输给的(x)个人的分数少了，那就让他们都去赢(i)，这样他们的分数也就守恒了，此时发现(i)分数又不守恒了，少了(x)，恰好刚才(j)去输给i之前的人了(x)场，(i)正好去赢(x)场，这样大家的分数都守恒了。
(from here:) 戳这
所以我们可以将前(k)大的分数定为(“strong king”),
接下来就是建图了:
我们首先定义一下变量：
int id[101][101];//两两比赛的编号
int b[200001];//分数
我们将((i,j))之间的比赛定义为(x)，每个队伍设为(y[i])。
- 将(s->x)连一条流量为(1)的边,(y->t)连一条流量为(b[y])的边
- 对于每一场比赛我们都有三种情况
- (b[i]<b[j])并且(i)为(“strong king”)，比赛的结果已经固定了,就是(i)胜利,将(x->y[i])连一条流量为(1)的边
- (b[j]<b[i])并且(j)为(“strong king”)，比赛的结果也已经固定了,就是(j)胜利,将(x->y[j])连一条流量为(1)的边
- 其他情况，比赛的结果不固定，所以要向(y[i])和(y[j])分别连一条流量为(1)的边
最后统计一下最大流就好了，判断一下最大流是不是等于(n*(n-1)/2)，如果等于那么(“strong king”)的个数就合法
(code)
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define inf 1e9
using namespace std;
typedef long long ll;
int head[100001],cnt,n,m,s,t=1000,x,y,z,dep[100001],id[101][101],b[200001];
struct node{
int to,next,v;
}a[200001];
void add(int x,int y,int c){
a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;
a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,head[y]=cnt;
}
queue<int> q;
int bfs(){
memset(dep,0,sizeof(dep));
q.push(s);
dep[s]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].next){
int v=a[i].to;
if(!dep[v]&&a[i].v>0)
dep[v]=dep[now]+1,q.push(v);
}
}
if(dep[t])
return 1;
return 0;
}
int dfs(int k,int list){
if(k==t||!list)
return list;
for(int i=head[k];i;i=a[i].next){
int v=a[i].to;
if(dep[v]==dep[k]+1&&a[i].v>0){
int p=dfs(v,min(list,a[i].v));
if(p){
a[i].v-=p;
if(i&1)
a[i+1].v+=p;
else a[i-1].v+=p;
return p;
}
}
}
dep[k]=0;
return 0;
}
int Dinic(){
int ans=0,k;
while(bfs())
while((k=dfs(s,inf)))
ans+=k;
return ans;
}
void init(int k){
memset(head,0,sizeof(head)),cnt=0;
for(int i=1;i<=n;i++)
add(i,t,b[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
add(s,id[i][j],1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(b[i]<b[j]&&i>n-k)
add(id[i][j],i,1);
else
if(b[i]>b[j]&&j>n-k)
add(id[i][j],j,1);
else
add(id[i][j],j,1),add(id[i][j],i,1);
}
}
bool check(int k){
init(k);
return (Dinic()==n*(n-1)/2);
}
char c[100001];
int main(){
int T;
scanf("%d%*c",&T);
while(T--){
int tot=0;n=0;
gets(c);
for(int i=0;i<strlen(c);i++){
if(i==0)
b[++n]=c[i]-'0';
else
if(c[i-1]==' '&&c[i]>='0'&&c[i]<='9')
b[++n]=c[i]-'0';
else
if(c[i-1]>='0'&&c[i-1]<='9'&&c[i]>='0'&&c[i]<='9')
b[n]=b[n]*10+c[i]-'0';
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
id[i][j]=id[j][i]=++tot+n;
for(int i=n;i;i--)
if(check(i)){ printf("%d
",i);break;}
}
}