P1264题解

· · 题解

题目大意

给你一个球队现在的胜利场次（失败场次屁用没有），以及没有进行的比赛 a_{i,j}，找出可能成为胜利次数最多的球队。

建模

很明显，一个队跑一次最大流，当前队（现在跑网络流的队伍）能夺冠的条件就是其他队的胜利数都小于等于当前队的最大胜利数（废话）。

我们将当前队的最大胜利数表示为 mx，第 i 队的胜利上限为 lim_{i}，则 lim_{i}=mx-w_{i}。

将每场比赛离散化一下，从源点向每个比赛连边，每个比赛向两个队连边，流量都为这两个队比赛的次数 a_{i,j}。

每个队向汇点连边，流量为当前队（设当前队为 x）的最大胜利次数减去其他队的胜利数 w_{x}-w_{i}+\sum_{i=1}^{n}a_{x,i}。

最后只要判断最大流是不是当前队的最大胜利次数即可。

注意：

Code

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int M = 2e4 + 10;
struct edge {
    int u, v, c, val, nxt;
    edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0): u(u), v(v), c(c), val(val), nxt(nxt) {}
} e[M];
int cnt = 1;
int head[N];
void ADD(int u, int v, int c, int val = 0) {
    cnt++;
    e[cnt] = edge(u, v, c, val, head[u]);
    head[u] = cnt;
}
void add_edge(int u, int v, int c, int val = 0) {
    ADD(u, v, c, val);
    ADD(v, u, 0, -val);
}
int dep[N];
int n;
int s, t, tot;
int now[N];
int a[100][100];
int loc[100][100];
int w[N];
bool bfs() {
    memset(dep, 0, sizeof dep);
    memcpy(now, head, sizeof head);
    dep[s] = 1;
    queue<int>q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            int c = e[i].c;
            if (!c || dep[v] != 0)continue;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    return dep[t];
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    for (int i = now[u]; i; i = e[i].nxt) {
        now[u] = i;
        int v = e[i].v;
        int c = e[i].c;
        if (!c || dep[v] != dep[u] + 1) continue;
        int ff = dfs(v, t, min(flow, c));
        if (ff) return e[i].c -= ff, e[i ^ 1].c += ff, ff;
    }
    return 0;
}
int maxflow() {
    int ans = 0;
    while (bfs()) {
        int nowflow;
        while ((nowflow = dfs(s, t, inf))) ans += nowflow;
    }
    return ans;
}
void work(int x) {
    cnt = 1;
    memset(head, 0, sizeof head);
    int mx = w[x];
    int ans = 0;
    for (int i = 1; i <= n; i++) mx += a[x][i];
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        if (w[i] > mx) return;
        add_edge(i, t, mx - w[i]);
        for (int j = 1; j < i; j++) {
            if (j != x && a[i][j]) {
                add_edge(s, loc[i][j], a[i][j]);
                add_edge(loc[i][j], i, a[i][j]);
                add_edge(loc[i][j], j, a[i][j]);
                ans += a[i][j];
            }
        }
    }
    if (maxflow() == ans) cout << x << " ";
}
int main() {
    cin >> n;
    s = n + 1;
    t = n + 2;
    tot = t;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        int sb;
        cin >> sb;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) loc[i][j] = ++tot;
    for (int i = 1; i <= n; i++) work(i);
}