ACM寒假第七讲

一、Stockbroker Grapevine

设计思路

题目要求对于不同股票经纪人的数据集，以及联系人员，传递消息的时间，找到最短的传递时间，使得能够传递给所有人。典型的图问题，而且是有权图，于是想到利用弗洛伊德算法来做（谢天谢地这学期学了数据结构以及离散数学，弗洛伊德算法和迪杰斯特拉算法都不是一般的难），查找文档和参考网上资料，可以将弗洛伊德算法的代码形式进行填充，之后再对时间进行判断即可。

设计代码

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;
int T, n;
int A[100][100];

void Floyd() {//弗洛伊德算法，模板记下
	for (int k = 1; k <= T; k ++) {
		for (int i = 1; i <= T; i ++) {
			for (int j = 1; j <= T; j ++) {
				if ( A[i][k] != INF && A[k][j] != INF && A[i][k] + A[k][j] < A[i][j]) {
					A[i][j] = A[i][k] + A[k][j];
				}
			}
		}
	}
}

int main() {
	int x, value;
	while (~scanf("%d", &T), T) {//由于一开始不知道矩阵多大，于是设计尽可能大
		for (int i = 0; i < 100; i ++) {
			for (int j = 0; j < 100; j ++) {
				A[i][j] = 100001;//初始化，设定很大的数字
			}
		}
		for (int i = 1; i <= T; i ++) {//键入值
			scanf("%d", &n);
			while (n --) {
				scanf("%d", &x);
				scanf("%d", &value);
				A[i][x] = value;
			}
		}
		Floyd();//算法统计
		int time = 100001;
		int stock;
		int i;
		for (i = 1; i <= T; i ++) {//判断综合用时
			int sum = 0;
			for (int j = 1; j <= T; j ++) {
				if (i != j && A[i][j] > sum) {
					sum = A[i][j];
				}
			}
			if (sum < time) {
				stock = i;
				time = sum;
			}
		}
		if (time == 1000001) {
			printf("disjoint\n");
		} else {
			printf("%d %d\n", stock, time);
		}
	}
	return 0;
}

二、树的直径

设计思路

题目要求对于一颗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
48
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+6;

vector<int> e[MAXN];
int d_all[MAXN];
int cnt_all[MAXN];

void dfs( int son, int father, int d, int cnt ) {
	int i;
	d_all[son] = d;
	cnt_all[son] = cnt;

	for ( i = 0; i < e[son].size(); i++ ) {
		if ( e[son][i] != father ) {
			dfs( e[son][i], son, d + 1, cnt + 1 );
		}
	}
}

int main() {
	int n, a, b, i, maxa, maxb;

	scanf("%d", &n);

	for ( i = 0; i < n - 1; i++ ) {
		scanf("%d%d", &a, &b);
		e[a].push_back( b );
		e[b].push_back( a );
	}
	dfs( 1, -1, 0, 0 );

	maxa = 1;
	for ( i = 1; i <= n; i++ ) {
		if ( d_all[i] > d_all[maxa] )
			maxa = i;
	}
	dfs( maxa, -1, 0, 0 );

	maxb = 1;
	for ( i = 1; i <= n; i++ ) {
		if ( d_all[i] > d_all[maxb] )
			maxb = i;
	}
	printf("%d\n", cnt_all[maxb]);

	return 0;
}

三、Invitation Cards

设计思路

题目简单来说，要求输入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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define N 1000000
int a[N + 10], b[N + 10], c[N + 10], n, m;
int dis[N + 10], vis[N + 10], first[N + 10], next[N + 10];

void dijkstra(int pos, int *a, int *b, int *c) {
	int i, j, min;
	for (i = 1; i <= n; i++)
		dis[i] = INT_MAX;
	memset(vis, 0, sizeof(vis));
	vis[pos] = 1;
	i = first[pos];
	while (i != -1) {
		dis[b[i]] = c[i];
		i = next[i];
	}
	dis[pos] = 0;
	for (i = 1; i < n; i++) {
		min = INT_MAX;
		for (j = 1; j <= n; j++)
			if (!vis[j] && dis[j] < min) {
				min = dis[j];
				pos = j;
			}
		vis[pos] = 1;
		j = first[pos];
		while (j != -1) {
			if (!vis[b[j]] && dis[pos] + c[j] < dis[b[j]])
				dis[b[j]] = dis[pos] + c[j];
			j = next[j];
		}
	}
}

void jiantu(int *a, int *b, int *c) {
	int i;
	memset(first, -1, sizeof(first));
	for (i = 1; i <= m; i++) {
		next[i] = first[a[i]];
		first[a[i]] = i;
	}
}

int main() {
	int T, i, sum;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (i = 1; i <= m; i++)
			scanf("%d%d%d", &a[i], &b[i], &c[i]);
		jiantu(a, b, c);
		dijkstra(1, a, b, c);
		sum = 0;
		for (i = 2; i <= n; i++)
			sum += dis[i];
		jiantu(b, a, c);        //反向建图
		dijkstra(1, b, a, c);   //记得传数组也得反向
		for (i = 2; i <= n; i++)
			sum += dis[i];
		printf("%d\n", sum);
	}
	return 0;
}

四、战略游戏

设计思路

这个题目主要要考虑给定了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
#include <bits/stdc++.h>
using namespace std;
int n, u, v, dp[10001][2];
vector<int> vec[100001];

void dfs(int fa, int x) {
	dp[x][1] = 1;
	for (int i = 0; i < vec[x].size(); i++)
		if (vec[x][i] != fa) {
			dfs(x, vec[x][i]);
			dp[x][0] += dp[vec[x][i]][1];
			dp[x][1] += min(dp[vec[x][i]][0], dp[vec[x][i]][1]);
		}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p >> u;
		for (int j = 1; j <= u; j++) {
			cin >> v;
			vec[p].push_back(v);
			vec[v].push_back(p);
		}
	}
	dfs(-1, 0);
	cout << min(dp[0][1], dp[0][0]);
	return 0;
}

五、学习总结

在这次C++代码中，初步认识了图论以及在其中的运用，重新认识了几个经典的图论相关算法。原本只是想来混德育分的但是感觉受益匪浅，希望在之后还能用到相关的知识，祝各位寒假愉快，谢谢大家。

Cpp
ACM寒假第七讲
https://gaster44.github.io/2025/02/19/ACM寒假第七讲/
作者
huangjinhong
发布于
2025年2月19日
许可协议