2022“杭电杯”中国大学生算法设计超级联赛（10）1001 // 最大流

题目来源：2022“杭电杯”中国大学生算法设计超级联赛（10）1001 - Winner Prediction

题目链接：Problem - 7244 (hdu.edu.cn)

题意

给定 \(T\) 组案例。

对于每组案例：

给定人数 \(n\)，已知结果的比赛场数 \(m_1\)，尚未进行的比赛场数 \(m_2\)。每场比赛，比赛双方中有且仅有一个胜者。在进行完所有比赛后，获胜场数最多的人为冠军（可并列冠军）。

若 \(1\) 号可能获得冠军输出 YES，否则输出 NO。

数据范围：\(1 \le T \le 100\)，\(1 \le n \le 500\)，\(1 \le m_1,m_2 \le 1000\).

思路：最大流

记 \(a_i\) 为 \(i\) 当前的获胜场数，对于未进行的比赛中有 \(1\) 参与的比赛，令 \(1\) 均获胜。

若 \(2\) 号 到 \(n\) 号中，有 \(a_i > a_1\)，直接可以知道答案为 NO。

再考虑一般情况。

因为要让 \(1\) 成为最终的冠军，\(i\) 最多只能再赢得 \(a_1 - a_i\) 场比赛。我们将剩下的比赛（假设有 \(m\) 场）和所有人视作点，从源点向每场比赛建立一条容量为 \(1\) 的边，每场比赛再向比赛双方各建一条容量为 \(1\) 的边，对于 \(2\) 到 \(n\) 中 的人，向汇点建一条容量为 \(a_1 - a_i\) 的边。

建图之后，dicnic求出最大流，若最大流等于 \(m\)，说明每场比赛都分配了输赢的结果，即存在让 \(1\) 成为冠军的可能，答案为 YES，否则为 NO。

时间复杂度：\(O(能过)\).

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1510;
const int M = (2000 + N) * 2;
const int INF = 0x3f3f3f3f;

int n, m1, m2, m, a[N], S, T;
pair<int,int> matchs[N];
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs()
{
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++ tt] = S, d[S] = 0, cur[S] = h[S];
    while(hh <= tt) {
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if(d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1, cur[ver] = h[ver];
                if(ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if(!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dicnic()
{
    int r = 0, flow;
    while(bfs()) {
        while(flow = find(S, INF)) r += flow;
    }
    return r;
}

void solve()
{
    memset(h, -1, sizeof h);
    idx = 0, m = 0;

    cin >> n >> m1 >> m2;
    for(int i = 1; i <= n; ++ i) a[i] = 0;
    for(int i = 1; i <= m1; ++ i) {
        int x, y, z;
        cin >> x >> y >> z;
        if(z) ++ a[x];
        else ++ a[y];
    }
    for(int i = 1; i <= m2; ++ i) {
        int x, y;
        cin >> x >> y;
        if(min(x, y) == 1) ++ a[1];
        else matchs[++ m] = { x, y };
    }

    for(int i = 2; i <= n; ++ i) {
        if(a[i] <= a[1]) continue;
        cout << "NO" << endl;
        return;
    }

    S = 0, T = n + m + 1;
    for(int i = 1; i <= m; ++ i) {
        int x = matchs[i].first, y = matchs[i].second;
        add(S, i, 1);
        add(i, m + x, 1), add(i, m + y, 1);
    }
    for(int i = 2; i <= n; ++ i) add(m + i, T, a[1] - a[i]);
    
    cout << (dicnic() == m ? "YES" : "NO") << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}