P1264 K-联赛 题解

发表于
很经典的网络流题

题目大意

已知每支队伍的胜场和待比赛的情况，求可能成为胜场最多的队伍个数（并列也算最多）。

解题思路

贪心：对于每支队伍，要想胜场最多，显然未参与的所有比赛都应获胜。

判断：枚举每支队伍，判断其他队伍的胜场能否不超过该队伍。

建图

考虑对比赛和队伍分别建点。

因为要保证所有其他队伍的胜场不超过当前枚举的队伍 $i$，所以从其他队伍向汇点连一条容量为该队伍还能获胜的最多场次，即 $W_i-w_j$ 的边（其中 $W_i$ 为队伍 $i$ 赢得所有比赛获得的胜场数，预处理出来）。

同时，对于每场比赛，向参与比赛的两支队伍分别连上容量为比赛场数，即 $a_{ij}$ 的边，再从源点向每场比赛连上相同容量的边。

此时的网络最大流表示在所有队伍胜场不超过队伍 $i$ 的前提下，能匹配的比赛场数。因此将网络最大流与队伍 $i$ 不参与的比赛场数进行比较，若相等则说明队伍 $i$ 可能获胜，输出即可。

处理细节

  • 建点连边时，要跳过当前枚举的队伍及其参加的比赛。

  • 连边时，每两个队伍间的比赛只连一条边。

  • 对于一支队伍 $i$，若存在另一支队伍 $j$ 使得 $w_j>W_i$，则显然队伍 $i$ 不可能成为胜场最多的队伍，此时不用跑网络流。

  • 若两支队伍之间已经没有比赛，则不需要连边。

  • 每次枚举要初始化。

丑陋的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <bits/stdc++.h>
using namespace std;
int n,sh[30],fu[30],maxm[30],sai[30][30],cnt=1,lst[100005],s,t,sum,pre,mid,dep[100005],now[100005],inf=0x3f3f3f3f;
struct edge{
	int f,t,val,lst;
	edge(int f=0,int t=0,int val=0,int lst=0):
		f(f),t(t),val(val),lst(lst){};
}e[100005];
void add(int u,int v,int val){
	e[++cnt]=edge(u,v,val,lst[u]);
	lst[u]=cnt;
	e[++cnt]=edge(v,u,0,lst[v]);
	lst[v]=cnt;
}
bool bfs(){
	memset(dep,-1,sizeof(dep));
	queue<int> q;
	q.push(s),dep[s]=0;
	while(!q.empty()){
		int u=q.front();
		now[u]=lst[u];
		q.pop();
		for(int i=lst[u];i;i=e[i].lst){
			int v=e[i].t;
			if(e[i].val&&dep[v]==-1){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=-1;
}
int dfs(int u,int in){
	if(u==t)return in;
	int out=0;
	for(int i=now[u];i;i=e[i].lst){
		now[u]=i;
		int v=e[i].t;
		if(e[i].val&&dep[v]==dep[u]+1){
			int go=dfs(v,min(in,e[i].val));
			e[i].val-=go;
			e[i^1].val+=go;
			in-=go,out+=go;
			if(go==0)dep[v]=-1;
			if(in==0)break;
		}
	}
	if(out==0)dep[u]=-1;
	return out;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>sh[i]>>fu[i];
	for(int i=1;i<=n;i++){
		maxm[i]=sh[i];
		for(int j=1;j<=n;j++){
			cin>>sai[i][j];
			maxm[i]+=sai[i][j];
			sum+=sai[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		bool fl=0;
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(sh[j]>maxm[i]){
				fl=1;
				break;
			}
		}
		if(fl)continue;
		s=0,t=(n-1)*(n-2)/2+n+1,mid=(n-1)*(n-2)/2;
		for(int j=0;j<=cnt;j++)e[j].f=e[j].t=e[j].val=lst[j]=e[j].lst=0;
		cnt=1,pre=0;
		for(int j=1;j<=n;j++){
			if(j==i)continue;
			add(mid+j,t,maxm[i]-sh[j]);
			for(int k=j+1;k<=n;k++){
				if(k==i)continue;
				add(0,++pre,sai[j][k]);
				add(pre,mid+j,inf);
				add(pre,mid+k,inf);
			}
		}
		int ans=0;
		while(bfs()){
			ans+=dfs(s,inf);
		}
		if(ans==sum/2-maxm[i]+sh[i])cout<<i<<' ';
	}
	return 0;
}