题面

有

n

n

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

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

给出每支队伍目前胜的场数

w

i

w_i

wi​ 和败的场数（没用），以及每两个队伍还剩下的比赛场数

a

i

,

j

a_{i,j}

ai,j​，确定所有可能得冠军的球队（获胜场数最多的得冠军，可以并列）。

n

≤

25

n\leq 25

n≤25，所有整数不超过 100 。

题解

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

1. 对于每两个队伍之间，新建一个点，从源点连来容量为

   a

   i

   ,

   j

   a_{i,j}

   ai,j​ 的边，再与

   i

   i

   i 和

   j

   j

   j 的代表点分别连容量正无穷的边，表示这

   a

   i

   ,

   j

   a_{i,j}

   ai,j​ 次比赛的胜利可以随意分配。

2. 从源点向每个

   i

   i

   i 的代表点连容量为

   w

   i

   w_i

   wi​ 的边，表示最初赢了

   w

   i

   w_i

   wi​ 场（如果不懒的话其实可以不用建这条边）。

3. 从每个

   i

   i

   i 的代表点向汇点连容量为

   L

   i

   L_i

   Li​ 的边，表示这个点赢不超过

   L

   i

   L_i

   Li​ 场是我们可以接受的。

若源点连出的边都满流，则方案合法，当我们把

L

i

L_i

Li​ 都设成正无穷时，我们就一定能找到一种最终获胜场数的可行解。

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

x

x

x 的最大获胜场数是

M

x

M_x

Mx​ ，存在方案使得其他团队的获胜场次不超过

M

x

M_x

Mx​ 。

那么我们就先令

L

x

=

+

∞

,

∀

i

≠

x

,

L

i

=

0

L_x=+\infty,\forall i\not=x,L_i=0

Lx​=+∞,∀i​=x,Li​=0 ，然后跑网络流，这时得到的流量就是

M

x

M_x

Mx​ ，然后令

L

x

=

+

∞

,

∀

i

≠

x

,

L

i

=

M

x

L_x=+\infty,\forall i\not=x,L_i=M_x

Lx​=+∞,∀i​=x,Li​=Mx​ ，跑网络流，看是否源点满流。

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;
}