题面

有 $n$ 支队伍进行比赛，每支队伍需要打的比赛数目相同。

每场比赛恰好一支队伍胜，另一支败。

给出每支队伍目前胜的场数 $w_i$ 和败的场数（没用），以及每两个队伍还剩下的比赛场数 $a_{i,j}$，确定所有可能得冠军的球队（获胜场数最多的得冠军，可以并列）。

$n\le 25$，所有整数不超过 100 。

题解

又是属于什么奇怪复杂度都能过的网络流题……

1. 对于每两个队伍之间，新建一个点，从源点连来容量为 $a_{i,j}$ 的边，再与 $i$ 和 $j$ 的代表点分别连容量正无穷的边，表示这 $a_{i,j}$ 次比赛的胜利可以随意分配。

2. 从源点向每个 $i$ 的代表点连容量为 $w_i$ 的边，表示最初赢了 $w_i$ 场（如果不懒的话其实可以不用建这条边）。

3. 从每个 $i$ 的代表点向汇点连容量为 $L_i$ 的边，表示这个点赢不超过 $L_i$ 场是我们可以接受的。

若源点连出的边都满流，则方案合法，当我们把 $L_i$ 都设成正无穷时，我们就一定能找到一种最终获胜场数的可行解。

如何判断某个队伍是否可夺冠呢？我们得主动地使之获胜场数最大化，同时让其他队伍获胜场数不超过它，也就是假设 $x$ 的最大获胜场数是 $M_x$ ，存在方案使得其他团队的获胜场次不超过 $M_x$ 。

那么我们就先令 $L_x=+\infty ,\forall i\ne x,L_i=0$ ，然后跑网络流，这时得到的流量就是 $M_x$ ，然后令 $L_x=+\infty ,\forall i\ne x,L_i=M_x$ ，跑网络流，看是否源点满流。

CODE

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1055
#define MAXM 40005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
LL read() {LL f=1,x=0;int s = getchar();while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48);s = getchar();}return f * x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);};
void putnum(LL x) {if(!x) {putchar('0');return ;}if(x<0) putchar('-'),x = -x;return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}int n,m,s,o,k;
int ip[30],ie[30][30],ep[30];
int S,T,cnt;
int hd[MAXN],v[MAXM],nx[MAXM],w0[MAXM],w[MAXM],cne,rev[MAXM];
int ins(int x,int y,int z) {nx[++cne]=hd[x]; v[cne]=y; w0[cne]=z; hd[x]=cne;nx[++cne]=hd[y]; v[cne]=x; w0[cne]=0; hd[y]=cne;rev[cne] = cne-1; rev[cne-1] = cne; return cne-1;
}
int hd2[MAXN],d[MAXN];
bool bfs() {for(int i = 1;i <= cnt;i ++) {d[i] = -1; hd2[i] = hd[i];}queue<int> b;b.push(S);d[S] = 0;while(!b.empty()) {int t = b.front();b.pop();if(t == T) return 1;for(int i = hd[t];i;i = nx[i]) {if(d[v[i]] < 0 && w[i] > 0) {d[v[i]] = d[t] + 1;b.push(v[i]);}}}return 0;
}
int dfs(int x,int fw) {if(x == T || !fw) return fw;int nw = 0;for(int i = hd2[x];i;i = nx[i]) {if(d[v[i]] == d[x] + 1 && w[i] > 0) {int nm = dfs(v[i],min(w[i],fw-nw));nw += nm; w[i] -= nm; w[rev[i]] += nm;if(nw == fw) break;}hd2[x] = nx[i];}return nw;
}
int dinic() {int ans = 0;while(bfs()) {ans += dfs(S,0x7f7f7f7f);}return ans;
}
void initdinic() {for(int i = 1;i <= cne;i ++) w[i] = w0[i];
}
int NWP() {hd[++ cnt] = 0; return cnt;}
int main() {int TS = read();while(TS --) {n = read();cne = 0; cnt = 0;S = NWP();T = NWP();int sm = 0;for(int i = 1;i <= n;i ++) {ip[i] = NWP();s = read();o = read();ins(S,ip[i],s);sm += s;}for(int i = 1;i <= n;i ++) {for(int j = 1;j <= n;j ++) {s = read();if(j < i) {sm += s;ie[i][j] = ie[j][i] = NWP();ins(S,ie[i][j],s);ins(ie[i][j],ip[i],0x3f3f3f3f);ins(ie[i][j],ip[j],0x3f3f3f3f);}}}for(int i = 1;i <= n;i ++) {ep[i] = ins(ip[i],T,0);}int fl = 0;for(int i = 1;i <= n;i ++) {w0[ep[i]] = 0x3f3f3f3f;initdinic();int lm = dinic();for(int j = 1;j <= n;j ++) {if(j != i) w[ep[j]] += lm;}int tt = lm + dinic();if(tt == sm) {if(fl) putchar(' ');putnum(i); fl = 1;}w0[ep[i]] = 0;}ENDL;}return 0;
}