[ABC241G] Round Robin

题意

$ N $ 名玩家进行循环赛。总共进行 $ \frac{N(N-1)}{2} $ 场比赛，比赛必然分出胜负，不存在平局，一场比赛中胜者获得 $ 1 $ 分。

当前进行了 $ M $ 场比赛，其中第 $ i $ 场 $ W_i $ 打败了 $ L_i $。

我们称一个玩家可能获胜当且仅当存在一种比赛结果使得该玩家的得分严格高于其它所有玩家。求哪些玩家可能获胜（按从小到大输出答案）。

题解

感觉这题还是有些东西的，其实在很早以前就做过这道题，但是在题单里再见到还是没做出来，有点难受。
但实际上这题的解法还是有值得学习的地方的。
先枚举胜利的人是谁，贪心的将所有没输的局面都设为赢。
我们接下来的目标就是寻找一种情况保证除钦定的之外最大的胜局数小于钦定的胜局数。
如果我们向网络流的方向思考，yy出一种比较常见的连边方法，将胜局数看作流量。
1.$s$ 向考试连一条流量为 $1$ 的边
2.考试对学生连边，若胜者已定，则考试向胜者连一条流量为 $1$ 的边，否则两人各连一条流量为 $1$ 的边。
3.学生向 $t$ 连一条流量为 $\infty$ 的边。
我们会发现一个问题，我们如果跑最大流的话最后的流量一定是 $n$ 。
这是一个和的关系，最大流无法判断最大胜局数是否符合条件，最大流只能保证每个考试都能分出胜负。
我们仔细思考这个过程，发现我们实际上也只有两个限制1.每场考试能分出胜负。2.最大胜局数符合条件。
但其实按照上面的连边方法第一个条件是必定满足的，而这只是一个和的关系，实际上对于解题是无意义的，我们无法判断最大胜局数是否符合条件。
我们现在是满足条件一判断条件二，我们不妨将两者替换一下，我们将人除钦定的外连向 $t$ 的边的流量修改为 $mx-1$，钦定的修改为 $mx$。
这样我们就强制让最大胜局数符合条件了，而是否成立就看最大流是否等于 $ \frac{n(n-1)}{2} $ 即可。

code

#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
const int N = 20005 ;
const int M = 100005 ;
const int INF = 1e9+7 ;
int n,m,tot,s,t,cnt = 1 ;
int dep[N],vis[N],win[N/10][N/10] ;
struct Edge{int v,w ;}E[2*M] ;
vector<int>ans,e[N] ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int fk(0) ; rg char c(gc()) ;
    while(!isdigit(c)) fk |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (fk?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; space ;
    print(p...) ;
}
inline void Add(int u,int v,int w)
{
	E[++cnt] = {v,w},e[u].pb(cnt) ;
	E[++cnt] = {u,0},e[v].pb(cnt) ;
}
inline int Bfs()
{
	me(dep,0x3f),me(vis,0),dep[s] = 0 ;
	queue<int>q ; q.push(s) ;
	while(!q.empty())
	{
		int x = q.front() ; q.pop() ;
		for(auto id:e[x])
		{
			int v = E[id].v,w = E[id].w ;
			if(!w || dep[x]+1 >= dep[v]) continue ;
			dep[v] = dep[x]+1 ;
			if(v == t)return 1 ;
			if(!vis[v]) q.push(v),vis[v] = 1 ;
		}
	}
	if(dep[t] == dep[0]) return 0 ;
	return 1 ;
}
int Dfs(int x,int flow)
{
	if(x == t) return flow ;
	int us = 0 ;
	for(auto id:e[x])
	{
		int v = E[id].v,w = E[id].w ;
		if(!w || dep[x]+1 != dep[v]) continue ;
		int low = Dfs(v,min(w,flow-us)) ;
		if(low) us += low,E[id].w -= low,E[id^1].w += low ;
		if(us == flow) break ;
	}
	if(!us) dep[x] = 0 ;
	return us ;
}
inline void Solve(int x)
{
	int winwin = 0 ; cnt = 1 ;
	FOR(i,1,n,1) e[i].clear() ;
	FOR(i,1,n,1) FOR(j,i+1,n,1)
	{
		if(win[i][j] == 1) Add(i*n+j,i,1) ;
		if(win[i][j] == 0) Add(i*n+j,i,1),Add(i*n+j,j,1) ;
		if(win[i][j] == -1) Add(i*n+j,j,1) ;
		if(win[i][j] == -1 && i == x) winwin++ ;
		if(win[i][j] == 1 && j == x) winwin++ ;
	}
	winwin = n-winwin-2 ;
	FOR(i,1,n,1) FOR(j,i+1,n,1) Add(s,i*n+j,1) ;
	FOR(i,1,n,1) 
		if(i != x) Add(i,t,winwin) ;
		else Add(i,t,winwin+1) ;
	int res = 0 ; while(Bfs()) res += Dfs(s,INF) ;
	if(res == n*(n-1)/2) ans.pb(x) ;
}
signed main()
{
//	freopen(".in","r",stdin) ;
//	freopen(".out","w",stdout) ;
	read(n,tot),s = n*n+n+1,t = s+1 ;
	FOR(i,1,tot,1)
	{
		int u,v,rp = 1 ; read(u,v) ;
		if(u > v) swap(u,v),rp = -rp ; win[u][v] = rp ;
	}
	FOR(i,1,n,1) Solve(i) ;
	for(auto v:ans) print(v) ;
    return 0 ;
}