AcWing 算法提高第三章图论

欧拉回路与欧拉路径

一笔画条件：起点边数 = 奇数，终点边数 = 奇数，中间点边数= 偶数。

欧拉回路:终点就是起点一、无向图 1 存在欧拉路径的充要条件 : 度数为奇数的点只能有0或2个 2 存在欧拉回路的充要条件 : 度数为奇数的点只能有0个二、有向图 1 存在欧拉路径的充要条件 : 要么所有点的出度均==入度；要么除了两个点之外，其余所有点的出度==入度剩余的两个点:一个满足出度-入度==1(起点) 一个满足入度-出度==1(终点) 2 存在欧拉回路的充要条件 : 所有点的出度均等于入度

1123. 铲雪车

题意：在双向道铲雪，每条边都要铲两次，求最少铲雪时间。

双向道说明出度=入度，必然存在欧拉回路，直接求路径长度乘 2 然后计算时间即可。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;

int s, t, u, v;
double sum;

int main() 
{
	cin >> s >> t;
	while (cin >> s >> t >> u >> v) {
		double dx = s - u;
		double dy = t - v;
		sum += sqrt(dx * dx + dy * dy) * 2;
	}
	int minutes = round(sum / 1000 / 20 * 60);
	int hours = minutes / 60;
	minutes %= 60;
	printf("%d:%02d\n", hours, minutes);
    return 0;
}

拓扑排序

1191. 家谱树

题意：模板题，求 $n$ 个点有向图的拓扑序。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 105, M = N * N / 2;

int n, tot, cnt;
int ver[M], nxt[M], head[N], ind[N];
int a[N];

void add(int x, int y) {
	ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}

void topsort() {
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		if (!ind[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		a[++cnt] = x;
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (--ind[y] == 0) q.push(y);
		}
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	int x;
	for (int i = 1; i <= n; ++i) {
		while (cin >> x, x) {
			add(i, x);
			ind[x]++;
		}
	}
	topsort();
	for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
    return 0;
}

1192. 奖金

题意：$n(1\le x\le10000)$ 个员工，$m(1\le m\le20000)$ 个要求，每个要求 a b 表示 a 员工比 b 员工奖金高，每位员工奖金最少为 $100$ 元。

差分约束系统，边权为正，拓扑序求最长路。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5, M = 2e4 + 5;

int n, m, tot, cnt;
int ver[M], nxt[M], head[N];
int ind[N], a[N], pri[N];

void add(int x, int y) {
	ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int topsort() {
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		if (!ind[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		a[++cnt] = x;
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (--ind[y] == 0) q.push(y);
		}
	}
	return cnt == n;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int x, y;
	for (int i = 1; i <= m; ++i) {
		cin >> x >> y;
		add(y, x);
		ind[x]++;
	}
	if (!topsort()) { cout << "Poor Xed\n"; exit(0); }
	for (int i = 1; i <= n; ++i) pri[i] = 100;
	for (int i = 1; i <= n; ++i) {
		int x = a[i];
		for (int j = head[x]; j; j = nxt[j]) {
			int y = ver[j];
			pri[y] = max(pri[y], pri[x] + 1);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans += pri[i];
	cout << ans << '\n';
    return 0;
}

AcWing 164. 可达性统计

题意：$n$ 个点 $m$ 条边的有向无环图($1\le n,m\le30000$)，统计从每个点出发能到达的点的数量。

利用拓扑序的逆序计算，每个点后继结点答案并集+1为该点答案，用bitset状态压缩求解，f[x] 第 i 位为 1 表示从 x 能到 i，最后求每个 x 中 1 的数量。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 3e4 + 5, M = N;

int n, m, tot, cnt;
int ver[M], nxt[M], head[N]; 
int ind[N], a[N];
bitset<N> f[N];

void add(int x, int y) {
	ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void topsort() {
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		if (!ind[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		a[++cnt] = x;
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (--ind[y] == 0) q.push(y);
		}
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int x, y;
	for (int i = 1; i <= m; ++i) {
		cin >> x >> y;
		add(x, y);
		ind[y]++;
	}
	topsort();
	for (int i = n; i; --i) {
		int x = a[i];
		f[x][x] = 1;
		for (int j = head[x]; j; j = nxt[j]) {
			int y = ver[j];
			f[x] |= f[y]; 
		}
	}
	for (int i = 1; i <= n; ++i)
		cout << f[i].count() << '\n';
    return 0;
}

456. 车站分级

题意：$n$ 个火车站，每个火车站一个级别，最低为 1，如果火车站经过 $x$，始发站、终点站之间所有大于等于 x 的火车站必须停靠，$m$ 趟列车，第 $i$ 趟 $s_i$ 个停靠站，求 $n$ 个火车站最少划分的级别数。

差分约束，未停靠的一定小于停靠的，最坏 $1000$ 个火车站和列车，每趟 $500$ 个停靠，有 $500\times500\times1000=2.5\times10^8$ 条边，考虑两个集合中的点连虚拟点来优化。

 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


#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int N = 2005, M = 1e6 + 5;

int n, m, tot, cnt;
int ver[M], edge[M], nxt[M], head[N];
int ind[N], a[N], vis[N], level[N];

void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
	ind[y]++;
}

void topsort() {
	queue<int> q;
	for (int i = 1; i <= n + m; ++i)
		if (!ind[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		a[++cnt] = x;
		for (int i = head[x]; i; i = nxt[i]) {
			int y = ver[i];
			if (--ind[y] == 0) q.push(y);
		}
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int k, x, st, ed;
	for (int i = 1; i <= m; ++i) {
		memset(vis, 0, sizeof(vis));
		cin >> k;
		for (int j = 1; j <= k; ++j) {
			cin >> x;
			if (j == 1) st = x;
			else if (j == k) ed = x;
			vis[x] = 1;
		}
		int tmp = n + i;
		for (int j = st; j <= ed; ++j) {
			if (!vis[j]) add(j, tmp, 0);
			else add(tmp, j, 1);
		}
	}
	topsort();
	for (int i = 1; i <= n; ++i) level[i] = 1;
	for (int i = 1; i <= n + m; ++i) {
		int x = a[i];
		for (int j = head[x]; j; j = nxt[j]) {
			int y = ver[j];
			level[y] = max(level[y], level[x] + edge[j]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, level[i]);
	cout << ans << '\n';
    return 0;
}

Contents

欧拉回路与欧拉路径

拓扑排序