最小路径覆盖

发表于 | Edited on | 分类于 | 次阅读

题目来源：http://algorithm.openjudge.cn/2017mock/H/

解题思路：

  • 对于图G = （V，E）来说使用最少的路径，使得这些路径中的顶点互不相交并且这些路径中顶点的集合恰好时这个图的顶点。
  • 假设一条路径都没有，此时覆盖原图需要|V|条路径（每个顶点算作一个路径）。
  • 一旦两个顶点之间存在1条路径，那么需要的路径就会减少1条，因为1条边可以覆盖2个顶点。因此如果有K条这样的路径，那么就能够减少K条路径（1条路径可以减少额外的1个用于覆盖的顶点）。
  • 网上大神特别巧妙的思路，将一个定点划分为两部分，V划分为V1和V2， 将V1视作出边，V2视作入边。假如顶点U和V之间有连边，则连接U1和V2，将所有的出边和超级源点S连接，容量为1，将所有的入边和超级汇点T连接，容量为1，求该网络流的最大流，最后用|V|-maxFlow即为最小的路径覆盖数。

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/*
* Dinic algo for max flow
*
* This implementation assumes that #nodes, #edges, and capacity on each edge <= INT_MAX,
* which means INT_MAX is the best approximation of INF on edge capacity.
* The total amount of max flow computed can be up to LLONG_MAX (not defined in this file),
* but each 'dfs' call in 'dinic' can return <= INT_MAX flow value.
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

#define N (1000+2)
#define M (2*N*N+4*N)

using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;

struct edge {
	int v, cap, next;
};
edge e[M];

int head[N], level[N], cur[N];
int num_of_edges;

/*
* When there are multiple test sets, you need to re-initialize before each
*/
void dinic_init(void) {
	num_of_edges = 0;
	memset(head, -1, sizeof(head));
	return;
}

int add_edge(int u, int v, int c1, int c2) {
	int& i = num_of_edges;

	assert(c1 >= 0 && c2 >= 0 && c1 + c2 >= 0); // check for possibility of overflow
	e[i].v = v;
	e[i].cap = c1;
	e[i].next = head[u];
	head[u] = i++;

	e[i].v = u;
	e[i].cap = c2;
	e[i].next = head[v];
	head[v] = i++;
	return i;
}

void print_graph(int n) {
	for (int u = 0; u < n; u++) {
		printf("%d: ", u);
		for (int i = head[u]; i >= 0; i = e[i].next) {
			printf("%d(%d)", e[i].v, e[i].cap);
		}
		printf("\n");
	}
	return;
}

/*
* Find all augmentation paths in the current level graph
* This is the recursive version
*/
int dfs(int u, int t, int bn) {
	if (u == t) return bn;
	int left = bn;
	for (int &i = cur[u]; i >= 0; i = e[i].next) {
		int v = e[i].v;
		int c = e[i].cap;
		if (c > 0 && level[u] + 1 == level[v]) {
			int flow = dfs(v, t, min(left, c));
			if (flow > 0) {
				e[i].cap -= flow;
				e[i ^ 1].cap += flow;
				cur[u] = i;
				left -= flow;
				if (!left) break;
			}
		}
	}
	if (left > 0) level[u] = 0;
	return bn - left;
}

bool bfs(int s, int t) {
	memset(level, 0, sizeof(level));
	level[s] = 1;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == t) return true;
		for (int i = head[u]; i >= 0; i = e[i].next) {
			int v = e[i].v;
			if (!level[v] && e[i].cap > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return false;
}

LL dinic(int s, int t) {
	LL max_flow = 0;

	while (bfs(s, t)) {
		memcpy(cur, head, sizeof(head));
		max_flow += dfs(s, t, INT_MAX);
	}
	return max_flow;
}

int upstream(int s, int n) {
	int cnt = 0;
	vector<bool> visited(n);
	queue<int> q;
	visited[s] = true;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i >= 0; i = e[i].next) {
			int v = e[i].v;
			if (e[i].cap > 0 && !visited[v]) {
				visited[v] = true;
				q.push(v);
				cnt++;
			}
		}
	}
	return cnt; // excluding s
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m, n;
	cin >> m >> n;
	int s = 0, t = 2 * n + 1;
	dinic_init();
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		add_edge(a, b + n, 1, 0);
	}
	for (int i = 0; i < n; ++i) {
		add_edge(s, i + 1, 1, 0);
		add_edge(i + n + 1, t, 1, 0);
	}
	LL maxFlow = dinic(s, t);
	printf("%lld\n",n - maxFlow);
}
// 参考：https://blog.csdn.net/pengwill97/article/details/82765383