hdu7244-Winner Prediction（22多校第十场1001 dinic最大流）

梦开始的地方

启蒙题，场上看见这题后才开始学习流。

题意

$n$ 个人共进行 $m1+m2$ 场比赛，其中 $m1$ 场的结果已知，同时已知剩下 $m2$ 场中每场的参赛选手，问 $1$ 号是否有可能获胜（即没有其他选手的胜利场次大于它）

容易想到，在剩下的 $m2$ 场中，只要有 $1$ 号出场，那么一定贪心的使 $1$ 号全部获胜，则其他选手在剩下 $m2$ 场中的最多获胜次数为 $cnt[1]-cnt[i]$，其中 $cnt[i]$ 为 $i$ 号选手在前 $m1$ 场中的获胜次数。

建图通过源点 $s$ 向所有未比赛的场次（有 $1$ 号选手参加的不计入，下同）连容量为 $1$ 的边，场次向两个参赛选手连容量为 $1$ 的边，参赛选手向汇点 $t$ 连容量为 $cnt[1]-cnt[i]$ 的边，跑最大流判断是否等于未比赛场次。

参考代码

#include 
#define itn int
#define int long long
#define endl "\n"
#define PII pair<int, int>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const itn inf = 0x3f3f3f;
const int mod = 998244353;
// const int mod = 1e9 + 7;

int n, m, s, t;
int nex[M];

struct Edge {
    int from, to, cap, flow;
    Edge(int f, int t, int c, int fl) {
        from = f;
        to = t;
        cap = c;
        flow = fl;
    }
};

struct Dinic {
    int n, m, s, t;  //结点数，边数（包括反向弧），源点编号和汇点编号
    vector<Edge> edges;  //边表。edge[e]和edge[e^1]互为反向弧
    vector<int> G[N];  //邻接表，G[i][j]表示节点i和第j条边在e数组中的序号
    bool vis[N];  // BFS使用
    int d[N];     //从起点到i的距离
    int cur[N];   //当前弧下标

    void clear_all(int n) {
        for (int i = 0; i < n; i++)
            G[i].clear();
        edges.clear();
    }
    void clear_flow() {
        int len = edges.size();
        for (int i = 0; i < len; i++)
            edges[i].flow = 0;
    }
    void add_edge(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            int len = G[x].size();
            for (int i = 0; i < len; i++) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int a) {
        if (x == t || a == 0)
            return a;
        int flow = 0, f, len = G[x].size();
        for (int& i = cur[x]; i < len; i++) {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] &&
                (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0)
                    break;
            }
        }
        return flow;
    }
    int maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, inf);
        }
        return flow;
    }

    int mincut() {  // call this after maxflow
        int ans = 0;
        int len = edges.size();
        for (int i = 0; i < len; i++) {
            Edge& e = edges[i];
            if (vis[e.from] && !vis[e.to] && e.cap > 0)
                ans++;
        }
        return ans;
    }
    void reduce() {
        int len = edges.size();
        for (int i = 0; i < len; i++)
            edges[i].cap -= edges[i].flow;
    }
} dinic;

int cnt[N];

void solve() {
    itn n, m1, m2;
    cin >> n >> m1 >> m2;
    memset(cnt, 0, sizeof(cnt));
    dinic.clear_all(n + m2 + 10);
    int s = 0, t = n + m2 + 1;
    for (int i = 1; i <= m1; i++) {
        int x, y, op;
        cin >> x >> y >> op;
        if (op == 1)
            cnt[x]++;
        else
            cnt[y]++;
    }
    int sum = 0;
    for (int i = 1; i <= m2; i++) {
        int x, y;
        cin >> x >> y;
        if (x > y)
            swap(x, y);
        if (x == 1) {
            cnt[x]++;
            continue;
        }
        sum++;
        dinic.add_edge(s, i, 1);
        dinic.add_edge(i, x + m2, 1);
        dinic.add_edge(i, y + m2, 1);
    }
    int maxx = 0;
    for (int i = 2; i <= n; i++) {
        maxx = max(maxx, cnt[i]);
        dinic.add_edge(i + m2, t, cnt[1] - cnt[i]);
    }
    if (maxx > cnt[1]) {
        cout << "NO" << endl;
        return;
    }
    int ans = dinic.maxflow(s, t);
    // cout << ans << endl;
    if (ans == sum)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(12);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174