[LOJ#6002]「网络流 24 题」最小路径覆盖
试题描述
给定有向图 G=(V,E)。设 P 是 G 的一个简单路（顶点不相交）的集合。如果 V 中每个顶点恰好在 P 的一条路上，则称 P 是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始，长度也是任意的，特别地，可以为 0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。
设计一个有效算法求一个有向无环图 G 的最小路径覆盖。
输入
第 1 行有 2 个正整数 n 和 m。n 是给定有向无环图 G 的顶点数，m 是 G 的边数。
接下来的 m 行，每行有 2 个正整数 u 和 v，表示一条有向边 (i,j)。
接下来的 m 行，每行有 2 个正整数 u 和 v，表示一条有向边 (i,j)。
输出
从第 1 行开始，每行输出一条路径。
文件的最后一行是最少路径数。
文件的最后一行是最少路径数。
输入示例
11 12 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 11 10 11
输出示例
1 4 7 10 11 2 5 8 3 6 9 3
数据规模及约定
1≤n≤200,1≤m≤6000
题解
练一下 Dinic 模板。
最小路径覆盖是经典题了。
首先我们假定每个节点都是一个路径，考虑尽量多地合并某两条路径。
不难发现一条路径的贡献可以看成这条路径的节点个数减去边数，并且每个点只能属于一条路径，那么如果把原图上的每个点拆成入和出两个点，那么会发现这个问题转化成了二分图匹配，答案等于原图总点数 - 二分图最大匹配数。
对于所有入点没有被匹配上的点，就是原图中路径的起点，然后沿着这个起点不停地找“出点——入点”的匹配边，找出整个路径。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 410
#define maxm 12410
#define oo 2147483647
struct Edge {
int from, to, flow;
Edge() {}
Edge(int _1, int _2, int _3): from(_1), to(_2), flow(_3) {}
} ;
struct Dinic {
int n, m, s, t, head[maxn], nxt[maxm];
Edge es[maxm];
int vis[maxn], Q[maxn], hd, tl;
int cur[maxn];
void init() {
m = 0; memset(head, -1, sizeof(head));
return ;
}
void setn(int _n) {
n = _n;
return ;
}
void AddEdge(int a, int b, int c) {
es[m] = Edge(a, b, c); nxt[m] = head[a]; head[a] = m++;
es[m] = Edge(b, a, 0); nxt[m] = head[b]; head[b] = m++;
return ;
}
bool BFS() {
memset(vis, 0, sizeof(vis));
hd = tl = 0; Q[++tl] = s; vis[s] = 1;
while(hd < tl) {
int u = Q[++hd];
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(!vis[e.to] && e.flow) vis[e.to] = vis[u] + 1, Q[++tl] = e.to;
}
}
return vis[t] > 1;
}
int DFS(int u, int a) {
if(u == t || !a) return a;
int flow = 0, f;
for(int& i = cur[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(vis[e.to] == vis[u] + 1 && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s; t = _t;
int flow = 0;
while(BFS()) {
for(int i = 1; i <= n; i++) cur[i] = head[i];
flow += DFS(s, oo);
}
return flow;
}
} sol;
int CntP;
struct Point {
int id;
Point(): id(0) {}
int p() { return id ? id : id = ++CntP; }
} inu[maxn], outu[maxn], S, T;
int tmp[maxn], cntt, uid[maxn];
int main() {
int n = read(), m = read();
sol.init(); S.p(); T.p();
for(int i = 1; i <= n; i++)
sol.AddEdge(S.p(), outu[i].p(), 1), uid[outu[i].p()] = i,
sol.AddEdge(inu[i].p(), T.p(), 1), uid[inu[i].p()] = i;
for(int i = 1; i <= m; i++) {
int a = read(), b = read();
sol.AddEdge(outu[a].p(), inu[b].p(), 1);
}
sol.setn(CntP);
int ans = n - sol.MaxFlow(S.p(), T.p());
for(int i = 1; i <= n; i++) {
bool iss = 0;
for(int t = sol.head[inu[i].p()]; t != -1; t = sol.nxt[t]) {
Edge& e = sol.es[t];
if(e.to == T.p() && e.flow){ iss = 1; break; }
}
if(!iss) continue;
int node = i; cntt = 0; tmp[++cntt] = node;
for(;;) {
bool has = 0;
for(int t = sol.head[outu[node].p()]; t != -1; t = sol.nxt[t]) {
Edge& e = sol.es[t];
if(e.to != S.p() && !e.flow){ has = 1; tmp[++cntt] = node = uid[e.to]; break; }
}
if(!has) break;
}
for(int i = 1; i <= cntt; i++) printf("%d%c", tmp[i], i < cntt ? ' ' : '
');
}
printf("%d
", ans);
return 0;
}