假设当前在确定玩家 \(p\) 是否能成为唯一的赢家。
假设 \(p\) 能赢下所有不确定的比赛，令 \(win\) 表示他赢的数量。
如果 \(win=0\) 显然他不能成为唯一的赢家，下面都假设 \(win\ge1\)。
考虑网络流建图。
建立源点 \(S\)，汇点 \(T\)，\(A_{i,j}\) 表示玩家 \(i\) 与 \(j\) 之间的比赛，\(B_i\) 表示玩家 \(i\)。
约定 \((u,v,w)\) 表示 \(u\) 连向 \(v\) 的流量为 \(w\) 的边。
- \(S\) 向每场比赛连边：\((S,A_{i,j},1)\)
- 对于每场比赛 \(A_{i,j}\)，如果 \(i\) 赢了，那么 \((A_{i,j},B_i,1)\)，否则如果 \(j\) 赢了，那么 \((A_{i,j},B_j,1)\)，否则 \((A_{i,j},B_i,1),(A_{i,j},B_j,1)\)
- 玩家 \(p\) 向 \(T\) 连流量为 \(win\) 的边，\((B_p,T,win)\)
- 其余玩家向 \(T\) 连流量为 \(win-1\) 的边，\((B_i(i\ne p),T,win-1)\)
然后跑一遍最大流，看看是否满流，满流就说明存在方案使得 \(p\) 成为唯一的赢家。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 55, inf = 0x3f3f3f3f;
int n, m;
int G[N][N];
int a[N][N], b[N];
int head[N*N], ver[N*N*N], wei[N*N*N], nxt[N*N*N], cnt;
int S, T;
int d[N*N];
void add(int u, int v, int w) {
ver[++cnt] = v, wei[cnt] = w, nxt[cnt] = head[u], head[u] = cnt;
ver[++cnt] = u, wei[cnt] = 0, nxt[cnt] = head[v], head[v] = cnt;
}
bool bfs() {
memset(d, 0, sizeof d), d[S] = 1;
queue <int> q; q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (wei[i] && !d[v]) {
d[v] = d[u] + 1;
q.push(v);
if (v == T) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == T) return flow;
int res = flow;
for (int i = head[u]; i && res; i = nxt[i]) {
int v = ver[i], w = wei[i];
if (w && d[v] == d[u] + 1) {
int k = dinic(v, min(flow, w));
if (!k) d[v] = 0;
wei[i] -= k, wei[i ^ 1] += k;
res -= k;
}
}
return flow - res;
}
bool check(int x) {
memset(head, 0, sizeof head), cnt = 1;
int win = 0;
for (int i = 1; i <= n; ++i) {
if (i == x) continue;
if (G[x][i] != -1) ++win;
}
if (!win) return false;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
add(S, a[i][j], 1);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j) {
if (G[i][j] == 1) add(a[i][j], b[i], 1);
else if (G[i][j] == -1) add(a[i][j], b[j], 1);
else add(a[i][j], b[i], 1), add(a[i][j], b[j], 1);
}
for (int i = 1; i <= n; ++i)
if (x == i) add(b[i], T, win);
else add(b[i], T, win - 1);
int sum = 0, flow;
while (bfs())
while (flow = dinic(S, inf)) sum += flow;
return sum == n * (n - 1) / 2;
}
int main() {
scanf("%d%d", &n, &m); S = 0, T = n * (n - 1) / 2 + n + 1;
int tot = 0;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
a[i][j] = ++tot;
for (int i = 1; i <= n; ++i) b[i] = ++tot;
for (int i = 1, u, v; i <= m; ++i) scanf("%d%d", &u, &v), G[u][v] = 1, G[v][u] = -1;
for (int i = 1; i <= n; ++i) if (check(i)) printf("%d ", i);
return 0;
}