yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P2764 最小路径覆盖问题

发表于 更新于 分类于

P2764 最小路径覆盖问题

题面

题目链接

解法

不妨先假设每个点都单独被一条路径覆盖，我们想要让最多的路径相连接。

对于每个点只能有最多一条入边和最多一条出边，而原图中有边的可以相连，建图方式显然，类似二分图，源点连向左边的点，右边的点连向汇点，流量为$1$，原图中的边$(u,v)$在网络中为$v$右边的连向$u$左边的，为便于输出方案流量设为$+\infty$。

AC代码

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
/**
 * @file:           P2764.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P2764
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 505;
const int MAXM = 2e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
    struct Edge {
        int v, flow;
    } edge[MAXM];
    int tot = 1, flow = 0;
    int head[MAXN], nxt[MAXM], lev[MAXN], cur[MAXN];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        memset(lev, -1, sizeof(lev));
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            memcpy(cur, head, sizeof(cur));
            flow += augment(s, t, INF);
        }
        return flow;
    }
};
int n, m, s, t, num, cnt, pre[MAXN], col[MAXN], pt[MAXN][2];
Dinic maxflow;
vector<int> answ[MAXN];
signed main() {
    read(n), read(m);
    s = ++num, t = ++num;
    for (int i = 1; i <= n; ++i)
        pt[i][0] = ++num, pt[i][1] = ++num;
    for (int i = 1; i <= n; ++i) {
        maxflow.addedge(s, pt[i][0], 1);
        maxflow.addedge(pt[i][1], t, 1);
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        read(u), read(v);
        maxflow.addedge(pt[u][0], pt[v][1], INF);
    }
    int ans = n - maxflow.maxflow(s, t);
    for (int u = 1; u <= n; ++u) {
        for (int i = maxflow.head[pt[u][0]]; i; i = maxflow.nxt[i])
            if (maxflow.edge[i].flow == INF - 1)
                pre[(maxflow.edge[i].v - 1) >> 1] = u;
    }
    for (int i = 1; i <= n; ++i) {
        if (!pre[i])
            col[i] = ++cnt;
        else
            col[i] = col[pre[i]];
        answ[col[i]].push_back(i);
    }
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j < answ[i].size(); ++j)
            write(answ[i][j]), putchar(" \n"[j == answ[i].size() - 1]);
    }
    write(ans), putchar('\n');
    return 0;
}