题目
有(n)支球队,互相之间已经进行了一些比赛。现在还有(m)场比赛未进行,
每场比赛胜者得2分,平局各得1分,负者不得分。
问是否存在一种方法使得球队(n)的得分比其他(n-1)支球队的得分都高。
(nleq 100,mleq 1000)
分析
要让(n)比其他人都大那么肯定所有和(n)有关的比赛都是(n)赢。
我们对每场比赛建一个点(u),从(S)向(u)连容量为2的边。
对每支队伍建一个点(v),从(v)向(T)连容量为(a[n]-a[v]-1)的边。
然后从每个比赛点(u)向那两支队伍连容量为2的边。
跑一遍最大流就可以出解,有解当且仅当满流。
如果没有平分的可能直接让所有容量除以2向下取整就可以了。
代码
for (rr int i=1;i<=n;++i) scanf("%d",&a[i]);
for (rr int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
if (x==n||y==n) a[n]+=2;
else add(S,i,2),add(i,x+n,2),add(i,y+n,2),++ans;
}
for (rr int i=1;i<n;++i) if (a[i]>=a[n]) return !puts("NO");
for (rr int i=1;i<n;++i) add(i+m,T,a[n]-a[i]-1);
return !puts((dinic()==ans*2)?"YES":"NO");