【网络流24题】最小路径覆盖问题

题目描述

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

输入格式

第一行有 22 个正整数 n 和 m 。 n 是给定GAP(有向无环图) G 的顶点数， m 是 G 的边数。接下来的 m 行,每行有两个正整数 i 和 j 表示一条有向边 (i,j)。

输出格式

从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。

输入输出样例

输入 #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

1 4 7 10 11
2 5 8
3 6 9
3

分析

如果全部点本身作为一条路径，那总共有 $n$ 条路径。任何两个点相连（一个点入度与出度最多为 $1$ )，都会使路径数减 $1$ ，现在就要让相连的点尽量多。
~~应该不难想到这是最大匹配问题~~（好吧有点难想？
将每个点 $i$ 拆成两个点 $i, i^{'}$ ，对于每条有向边 $(a, b)$ ，从 $a$ 到 $b^{'}$ 连一条边，表示这是一个匹配。如图。

这样，跑最大匹配，就是最多可以连的连边数。
最小路径覆盖 = 点数 - 最大匹配数

代码如下

#include <bits/stdc++.h>
#define N 100005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 2], e[N];
int du[N], dep[N], gap[N], h[N], v[N], sum, cnt = 1, ans, cur[N], p[N], ret, s, t, n, m, tot;
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void crr(int a, int b){
	e[++ret].a = a; e[ret].b = b; e[ret].n = p[a]; p[a] = ret;
}
void bfs(int a){
	int i, b;
	queue<int> q;
	dep[a] = 1;
	gap[1] = 1;
	q.push(a);
	while(!q.empty()){
		a = q.front();
		q.pop();
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;
			if(!dep[b]){
				dep[b] = dep[a] + 1;
				gap[dep[b]]++;
				q.push(b);
			}
		}
	}
}
int sap(int a, int flow){
	int i, b, c, w, used = 0;
	if(a == t) return flow;
	for(i = cur[a]; i; i = d[i].n){
		cur[a] = i;
		b = d[i].b;
		c = d[i].c;
		if(dep[a] == dep[b] + 1 && c > 0){
			if(w = sap(b, min(flow - used, c))){
				used += w;
				d[i].c -= w;
				d[i ^ 1].c += w;
			}
			if(used == flow) return used;
		}
	}
	gap[dep[a]]--;
	if(!gap[dep[a]]) dep[s] = tot + 5;
	dep[a]++;
	gap[dep[a]]++;
	return used;
}
void dfs(int a){
	int i, b, c;
	if(a != s && a != t) printf("%d ", a);
	for(i = p[a]; i; i = e[i].n){
		b = e[i].b;
		dfs(b);
	}
}
int main(){
	int i, j, a, b, c;
	scanf("%d%d", &n, &m);
	tot = n * 2 + 2;
	s = n * 2 + 1;
	t = n * 2 + 2;
	for(i = 1; i <= m; i++){
		scanf("%d%d", &a, &b);
		cr(a, b + n, 1);
		cr(b + n, a, 0);
	}
	for(i = 1; i <= n; i++) cr(s, i, 1), cr(i, s, 0);
	for(i = 1; i <= n; i++) cr(i + n, t, 1), cr(t, i + n, 0);
	bfs(t);
	while(dep[s] < tot + 1){
		for(i = 0; i <= tot; i++) cur[i] = h[i];
		ans += sap(s, inf);
	}
	for(i = 2; i <= cnt; i++){
		a = d[i].a;
		b = d[i].b;
		c = d[i].c;
		if(b == s || b == t || a == s || a == t) continue;
		if(a > n) continue;
		if(!c){
			//if(a > n) a -= n;
			b -= n;
			crr(a, b);
			du[b]++;
			//printf("===%d %d\n", a, b);
		}
	}
	for(i = 1; i <= n; i++){
		if(!du[i]){
			dfs(i);
			printf("\n");
		}
	}
	printf("%d", n - ans);
	return 0;
}

【网络流24题】 最小路径覆盖问题