1738: 最小路径覆盖问题 ——最小不相交路径覆盖

1738: 最小路径覆盖问题 ——最小不相交路径覆盖

题意：

给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个 顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶 点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少 的路径覆盖。 设计一个有效算法求一个有向无环图G 的最小路径覆盖。

思路：

把原图的每个点V拆成VxVx和VyVy两个点，如果有一条有向边A->B，那么就加边Ax−>ByAx−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

证明：

一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。

#include #include #include #include #include #include using namespace std;const int maxn = 1000;const int INF = 0x3f3f3f3f;struct Edge { int from, to, cap, flow;};struct Dinic { int s, t; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap) { edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); int x = edges.size(); G[from].push_back(x-2); G[to].push_back(x-1); } bool bfs() { memset(vis, 0, sizeof(vis)); queue q; q.push(s); d[s] = 0; vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[u] + 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; for (int &i = cur[x]; i < G[x].size(); 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; }}ac;vector G[maxn];bool vis[maxn];void dfs(int u) { if (vis[u]) return; vis[u] = true; printf("%d ", u); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; dfs(v); }}int main(){ ac.init(); int n, m; scanf("%d%d", &n, &m); int s = 0, t = 2*n+1; int u, v; for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); ac.addedge(u, v+n, 1); } for (int i = 1; i <= n; i++) { ac.addedge(s, i, 1); } for (int i = n+1; i <= n*2; i++) { ac.addedge(i, t, 1); } int ans = ac.maxflow(s, t); for (int i = 0; i < maxn; i++) G[i].clear(); for (int i = 0; i < m; i++) { if (ac.edges[i<<1].flow != 0) { int u = ac.edges[i<<1].from, v = ac.edges[i<<1].to; G[u].push_back(v-n); } } memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { if (vis[i]) continue; dfs(i); printf("\n"); } printf("%d\n", n-ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。