P2756 飞行员配对方案问题

P2756 飞行员配对方案问题 - 洛谷
二分图最大匹配，用最大流跑也没问题

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
signed main(){
    int n, m;
    cin >> m >> n;
    MaxFlow maxflow(n + 5);
    int s = n + 1;
    int t = n + 2;
    for(int i = 1; i <= m; i++){
        maxflow.add(s, i, 1);
    }
    for(int i = m + 1; i <= n; i++){
        maxflow.add(i, t, 1);
    }
    int u, v;
    while(cin >> u >> v){
        if(u == -1 && v == -1)break;
        maxflow.add(u, v, 1);
    }
    ll ans = maxflow.dinic(s, t);
    cout << ans << endl;
    for(int u = 1; u <= m; u++){
        for(auto [w, v, id] : maxflow.E[u]){
            if(w == 0 && v != s && v != t){
                cout << u << " " << v << endl;
            }
        }
    }

    return 0;
}