Problem surface

have n n n teams compete, and each team needs to play the same number of games.

Each game happens to be five wins for one team and five losses for the other.

Give the number of games each team has won so far w i w_i wi# and the number of games lost (useless), and the number of games left for each two teams a i , j a_{i,j} ai,j, determine all the teams that may win the championship (the team that wins the most games can win the Championship side by side).

n ≤ 25 n\leq 25 n ≤ 25, all integers shall not exceed 100.

Problem solution

It is a network flow problem that can pass any strange complexity

1. For every two teams, create a new point with a capacity of from the source point a i , j a_{i,j} The edge of ai,j ， and i i i and j j The representative points of j are respectively connected to the edges with positive infinite capacity, indicating this a i , j a_{i,j} AI, the victory of j# games can be distributed at will.

2. From source to each i i The representative point connection capacity of i is w i w_i The side of wi ， means that you won at first w i w_i wi} field (if you're not lazy, you don't have to build this side).

3. From each i i The connection capacity from representative point to sink point of i is L i L_i The edge of Li ， indicates that this point won't exceed L i L_i Li field is acceptable to us.

If the source point and the outgoing edge are full of flow, the scheme is legal L i L_i When Li ， are set to positive infinity, we must find a feasible solution to the number of final winning games.

How to judge whether a team can win the championship? We have to actively maximize the number of wins and keep the number of wins of other teams within it, that is, the assumption x x What is the maximum number of wins for x M x M_x Mx, there is a scheme so that other teams won no more than M x M_x Mx​ .

Then we'll take shillings L x = + ∞ , ∀ i ≠ x , L i = 0 L_x=+\infty,\forall i\not=x,L_i=0 Lx = + ∞, ∀ i  = x,Li = 0, and then run the network flow. At this time, the traffic obtained is M x M_x Mx, then make L x = + ∞ , ∀ i ≠ x , L i = M x L_x=+\infty,\forall i\not=x,L_i=M_x Lx = + ∞, ∀ i  = x,Li = Mx, run the network flow to see if the source point is full.

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