cses/cses_1695.cpp at main · EzElephant/cses · GitHub

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
#include <bits/extc++.h>
using namespace std;
template <typename T>
struct ISAP
{
    static const int MAXN = 1005;
    static const T INF = INT_MAX;
    int n; // 點數
    int d[MAXN], gap[MAXN], cur[MAXN];
    struct edge
    {
        int v, pre;
        T cap, r;
        edge(int v, int pre, T cap) : v(v), pre(pre), cap(cap), r(cap) {}
    };
    int g[MAXN];
    vector<edge> e;
    void init(int _n)
    {
        memset(g, -1, sizeof(int) * ((n = _n) + 1));
        e.clear();
    }
    void add_edge(int u, int v, T cap, bool directed = false)
    {
        e.push_back(edge(v, g[u], cap));
        g[u] = e.size() - 1;
        e.push_back(edge(u, g[v], directed ? 0 : cap));
        g[v] = e.size() - 1;
    }
    T dfs(int u, int s, int t, T CF = INF)
    {
        if (u == t)
            return CF;
        T tf = CF, df;
        for (int &i = cur[u]; ~i; i = e[i].pre)
        {
            if (e[i].r && d[u] == d[e[i].v] + 1)
            {
                df = dfs(e[i].v, s, t, min(tf, e[i].r));
                e[i].r -= df;
                e[i ^ 1].r += df;
                if (!(tf -= df) || d[s] == n)
                    return CF - tf;
            }
        }
        int mh = n;
        for (int i = cur[u] = g[u]; ~i; i = e[i].pre)
        {
            if (e[i].r && d[e[i].v] < mh)
                mh = d[e[i].v];
        }
        if (!--gap[d[u]])
            d[s] = n;
        else
            ++gap[d[u] = ++mh];
        return CF - tf;
    }
    T isap(int s, int t, bool clean = true)
    {
        memset(d, 0, sizeof(int) * (n + 1));
        memset(gap, 0, sizeof(int) * (n + 1));
        memcpy(cur, g, sizeof(int) * (n + 1));
        if (clean)
            for (size_t i = 0; i < e.size(); ++i)
                e[i].r = e[i].cap;
        T MF = 0;
        for (gap[0] = n; d[s] < n;)
            MF += dfs(s, s, t);
        return MF;
    }
    vector<int> cut_e; // 最小割邊集
    vector<pair<int, int>> c;
    bool vis[MAXN];
    void dfs_cut(int u)
    {
        vis[u] = 1; // 表示u屬於source的最小割集
        for (int i = g[u]; ~i; i = e[i].pre)
            if (e[i].r > 0 && !vis[e[i].v])
                dfs_cut(e[i].v);
    }
    T min_cut(int s, int t)
    {
        T ans = isap(s, t);
        memset(vis, 0, sizeof(bool) * (n + 1));
        dfs_cut(s), cut_e.clear();
        for (int u = 0; u <= n; ++u)
            if (vis[u])
                for (int i = g[u]; ~i; i = e[i].pre)
                    if (!vis[e[i].v])
                    {
                        cut_e.push_back(i);
                        c.emplace_back(u, e[i].v);
                    }
        return ans;
    }
    void print_ans()
    {
        for (auto [u, v] : c)
            cout << u << ' ' << v << '\n';
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ISAP<int> d;
    int n, m;
    cin >> n >> m;
    d.init(n);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        d.add_edge(u, v, 1);
    }
    cout << d.min_cut(1, n) << '\n';
    d.print_ans();

    return 0;
}