题目分析

题意简述

已知有 $n$ 支参加 K 联赛的足球队，每支球队 $i$（$1 \leq i \leq n$）目前的胜场数为 $w_i$，负场数为 $d_i$，并且每两支球队 $i$ 和 $j$（$1 \leq i, j \leq n$）之间还剩余 $a_{i,j}$ 场比赛未进行。每支球队在赛季中要参加相同数量的比赛，且比赛无平局。要求判断哪些球队有赢得联赛冠军的可能性（两支或多支球队可以共同获得冠军，即不存在其他球队胜场数超过该球队的情况），需要找出所有有可能夺冠的球队。

输入

• 输入包含 $T$ 个测试用例，测试用例数量 $T$ 在输入文件首行给出。
• 每个测试用例包含三行：
  1. 第一行是一个整数 $n$（$1 \leq n \leq 25$），表示球队数量。
  2. 第二行包含 $2n$ 个非负整数 $w_1, d_1, w_2, d_2, \cdots$，每个数最大为 $100$，其中 $w_i$ 和 $d_i$ 分别是球队 $i$ 的当前胜场数和负场数。
  3. 第三行包含 $n^2$ 个非负整数 $a_{1,1}, a_{1,2}, \cdots$，每个数最大为 $10$，其中 $a_{i,j}$ 是球队 $i$ 和球队 $j$ 之间剩余的比赛场数，且满足 $a_{i,j} = a_{j,i}$，当 $i = j$ 时，$a_{i,j} = 0$。一行中的整数由一个或多个空格分隔。

输出

每个测试用例输出一行，按球队编号升序包含所有有可能赢得联赛冠军的球队。

解题思路

网络流建模

将判断球队是否有夺冠可能性的问题转化为网络流问题。

1. 源点 $s$ 和汇点 $t$：设置源点 $s = 0$ 和汇点 $t = n * n + n + 1$。
2. 比赛节点：对于每两支球队 $i$ 和 $j$ 之间的剩余比赛，创建一个节点 $id = (i - 1) * n + j + n$，从源点 $s$ 向该节点连边，容量为剩余比赛场数 $a_{i,j}$。同时，该节点向球队 $i$ 和球队 $j$ 分别连边，容量为无穷大 $INF$。
3. 球队节点：对于每支球队 $i$，从球队节点向汇点 $t$ 连边，容量为假设当前要判断的球队 $x$ 赢得所有剩余比赛后的总胜场数 $sum$ 减去球队 $i$ 当前的胜场数 $w_i$。$sum$ 为当前要判断的球队 $x$ 的当前胜场数 $w[x]$ 加上 $x$ 与其他球队剩余比赛场数之和（即 $\sum_{i = 1}^{n} a[x][i]$）。

判断可行性

1. 对于每支球队 $x$，先判断如果 $x$ 赢得所有剩余比赛，其他球队当前胜场数 $w[i]$ 是否已经超过了这个总胜场数 $sum$，如果超过则直接返回 $0$，表示该球队不可能夺冠。
2. 构建网络流图后，计算从源点 $s$ 到汇点 $t$ 的最大流。如果最大流的值等于所有比赛的总场数（即 $\sum_{1 \leq i < j \leq n} a[i][j]$），则说明存在一种安排剩余比赛结果的方式，使得该球队 $x$ 可以夺冠（即不存在其他球队胜场数超过 $x$ 的情况），返回 $1$；否则返回 $0$。

遍历所有球队

遍历每一支球队 $i$（$1 \leq i \leq n$），调用 check 函数判断其是否有夺冠的可能性，如果有则输出该球队编号。

代码实现

#include<cstdio> 
#include<iostream> 
#include<cmath> 
#include<algorithm> 
#include<cstring> 
#include<cstdlib> 
#include<cctype> 
#include<vector> 
#include<queue> 
#include<assert.h> 
#include<ctime> 
using namespace std; 
#define enter puts("") 
#define space putchar(' ') 
#define Mem(a, x) memset(a, x, sizeof(a)) 
#define In inline 
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt) 
typedef long long ll; 
typedef double db; 
const int INF = 0x3f3f3f3f; 
const db eps = 1e-8; 
const int maxn = 30; 
const int maxN = 1e3 + 5; 
const int maxe = 1e4 + 5; 

In ll read() { 
    ll ans = 0; 
    char ch = getchar(), las = ' '; 
    while(!isdigit(ch)) las = ch, ch = getchar(); 
    while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 
    if(las == '-') ans = -ans; 
    return ans; 
} 

In void write(ll x) { 
    if(x < 0) x = -x, putchar('-'); 
    if(x >= 10) write(x / 10); 
    putchar(x % 10 + '0'); 
} 

int n, s, t, w[maxn], d[maxn], a[maxn][maxn]; 

struct Edge { 
    int nxt, to, cap, flow; 
}e[maxe]; 
int head[maxN], ecnt = -1; 

In void addEdge(int x, int y, int w) { 
    e[++ecnt] = (Edge){head[x], y, w, 0}; 
    head[x] = ecnt; 
    e[++ecnt] = (Edge){head[y], x, 0, 0}; 
    head[y] = ecnt; 
} 

int dis[maxN]; 
In bool bfs() { 
    Mem(dis, 0), dis[s] = 1; 
    queue<int> q; 
    q.push(s); 
    while(!q.empty()) { 
        int now = q.front(); 
        q.pop(); 
        for(int i = head[now], v; ~i; i = e[i].nxt) 
            if(e[i].cap > e[i].flow &&!dis[v = e[i].to]) 
                dis[v] = dis[now] + 1, q.push(v); 
    } 
    return dis[t]; 
} 

int cur[maxN]; 
In int dfs(int now, int res) { 
    if(now == t || res == 0) return res; 
    int flow = 0, f; 
    for(int& i = cur[now], v; ~i; i = e[i].nxt) { 
        if(dis[v = e[i].to] == dis[now] + 1 && (f = dfs(v, min(res, e[i].cap - e[i].flow))) > 0) { 
            e[i].flow += f, e[i ^ 1].flow -= f; 
            flow += f, res -= f; 
            if(res == 0) break; 
        } 
    } 
    return flow; 
} 

In int maxFlow() { 
    int flow = 0; 
    while(bfs()) { 
        memcpy(cur, head, sizeof(head)); 
        flow += dfs(s, INF); 
    } 
    return flow; 
} 

In bool check(int x) { 
    Mem(head, -1), ecnt = -1; 
    int sum = w[x]; 
    for(int i = 1; i <= n; ++i) sum += a[x][i]; 
    for(int i = 1; i <= n; ++i) 
        if(w[i] > sum) return 0; //及时x全赢，场数还没有i多 
    int flow = 0; 
    for(int i = 1; i <= n; ++i) 
        for(int j = i + 1; j <= n; ++j) { 
            int id = (i - 1) * n + j + n; 
            addEdge(s, id, a[i][j]); 
            addEdge(id, i, INF), addEdge(id, j, INF); 
            flow += a[i][j]; 
        } 
    for(int i = 1; i <= n; ++i) 
        addEdge(i, t, sum - w[i]); 
    return maxFlow() == flow; 
} 

int main() { 
    int T = read(); 
    while(T--) { 
        n = read(); 
        s = 0, t = n * n + n + 1; 
        for(int i = 1; i <= n; ++i) w[i] = read(), d[i] = read(); 
        for(int i = 1; i <= n; ++i) 
            for(int j = 1; j <= n; ++j) 
                a[i][j] = read(); 
        bool flg = 1; 
        for(int i = 1; i <= n; ++i) 
            if(check(i)) { 
                if(flg) flg = 0; 
                else space; 
                write(i); 
            } 
        enter; 
    } 
    return 0; 
}

代码说明

1. 输入处理
   • 使用自定义的 read 函数读取测试用例数量 $T$，对于每个测试用例，读取球队数量 $n$，源点 $s$ 设置为 $0$，汇点 $t$ 设置为 $n * n + n + 1$。
   • 读取每支球队的当前胜场数 $w[i]$ 和负场数 $d[i]$，以及每两支球队之间剩余的比赛场数 $a[i][j]$。
2. 网络流相关函数
   • addEdge 函数用于添加边，构建网络流图。
   • bfs 函数进行广度优先搜索，用于标记从源点可达的节点，并为 dfs 函数寻找增广路径做准备。
   • dfs 函数进行深度优先搜索，沿着增广路径更新流，找到最大流。
   • maxFlow 函数通过不断调用 bfs 和 dfs 函数，计算从源点到汇点的最大流。
3. 检查函数 check
   • 对每支球队 $x$，先计算其假设赢得所有剩余比赛后的总胜场数 $sum$，若其他球队当前胜场数 $w[i]$ 大于 $sum$，直接返回 $0$。
   • 构建网络流图，连接源点、比赛节点、球队节点和汇点，并设置相应的边容量。
   • 计算最大流，若最大流等于所有比赛的总场数，则返回 $1$，表示该球队有夺冠可能性；否则返回 $0$。
4. 主函数逻辑
   • 遍历每个测试用例，对于每个测试用例中的每支球队，调用 check 函数判断其是否有夺冠可能性，若有则按要求输出球队编号。