图
徐仓仓 Lv3
  2022-08-13 16:03:44 2022-08-13 16:03    

📅time:8.13 -

🍔题目：

1013 25 Battle Over Cities DFS or 并查集 求解连通分量个数
1021 25 Deepest Root DFS 连通分量 统计最深 做不出来
1034 30 Head of a Gang DFS or 并查集
1076 30 Forwards on Weibo DFS or BFS 统计数量
1003 25 Emergency
1018 30 Public Bike Management Dijkstra+DFS 我去真难
1030 30 Travel Plan Dijkstra 结点花费最少 输出一条路径 有手就行
1072 30 Gas Station
1087 30 All Roads Lead to Rome Dijkstra +DFS 结点权重

🤔注意很多题目的索引是从1开始的

图的遍历

DFS

深度搜索的同时记录深度

1
2
3
4
5
6
7
8
9
10
11
void DFS(int r,int depth) {
	if (depth <= D) {
		ans.insert(r);
	}
	if (depth > D) return;
	flag[r] = depth;
	for (int i = 0; i < G[r].size(); i++) {
		if ((!flag[G[r][i]])||flag[G[r][i]]>depth+1)
			DFS(G[r][i], depth + 1);
	}
}

BFS

连通分量个数

  1. 利用DFS计数

🎈 1013 Battle Over Cities

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void DFS(int r) {
	flag[r] = true;
	for (int i = 1; i <= N; i++) {
		if (!flag[i] && G[r][i]) {//未被访问并且联通
			DFS(i);
		}
	}
}
//……
for (int i = 0; i < K; i++) {
    int cnt = 0, city;
    cin >> city;
    fill(flag, flag + maxn, false);
    flag[city] = true;
    for (int i = 1; i <= N; i++) {
        if (!flag[i]) {
            cnt++;
            DFS(i);
        }
    }
}
  1. 利用并查集

🎈 1013 Battle Over Cities

构造邻接表图，遍历并合并集合。

  1. 最深根结点

🎈 1021 Deepest Root

一个无向无环图，输出其最深结点（最长路的起始和结尾）。

  • 是否全部连通：搜一次看看每个点是否都踩到。

  • 找最深节点： 两次深度优先搜索，随机一个结点DFS后保留最深的结点们，然后从这些结点中的其中任意一个开始DFS得到最深的结点们，这两个结点集合的并集就是所求 。

    ​ vUrTat.md.png

DFS统计最深：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DFS(int root, int d) {
	if (d > big) {
		big = d;
		far.clear();
		far.push_back(root);
	}
	else if (d == big) {
		far.push_back(root);
	}
	flag[root] = true;
	for (int i = 1; i <= N; i++) {
		if (!flag[i] && G[root][i])
			DFS(i, d + 1);
	}
}

acyclic ： 非周期的; 非循环的; 无环的; 非环状的;

alphabetical order

pair of : 一对;

respectively : 分别地; 分别; 各自; 顺序为; 依次为;

vertex

residential

recommendation

附录

1013 Battle Over Cities

DFS

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
#include<iostream>
using namespace std;
const int maxn = 1010;
int N, M, K, G[maxn][maxn];
bool flag[maxn];
void DFS(int r) {
	flag[r] = true;
	for (int i = 1; i <= N; i++) {
		if (!flag[i] && G[r][i]) {
			DFS(i);
		}
	}
}
int main() {
	cin >> N >> M >> K;
	int a, b;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		G[a][b] = G[b][a] = 1;
	}
	for (int i = 0; i < K; i++) {
		int cnt = 0, city;
		cin >> city;
		fill(flag, flag + maxn, false);
		flag[city] = true;
		for (int i = 1; i <= N; i++) {
			if (!flag[i]) {
				cnt++;
				DFS(i);
			}
		}
		cout << cnt - 1 << endl;
	}
}

并查集

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
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int maxn = 1010;
int N, M, K, F[maxn];
vector<int>G[maxn];
int findFather(int i) {
	int x = i;
	while (F[x] != x) x = F[x];
	//此时x是根节点
	while (F[i] != x) {
		int t = F[i];
		F[i] = x;
		i = t;
	}
	return x;
}
int main() {
	cin >> N >> M >> K;
	int a, b;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int city;
	for (int i = 0; i < K; i++) {
		cin >> city;
		for (int j = 1; j <= N; j++) {//初始化
			F[j] = j;
		}
		for (int j = 1; j <= N; j++) {
			if (j == city) continue;
			for (int k = 0; k < G[j].size(); k++) {
				if (G[j][k] == city) continue;
				int fa = findFather(j);
				int fb = findFather(G[j][k]);
				if (fa != fb) {
					F[fa] = fb;
				}
			}
		}
		set<int> roots;
		for (int j = 1; j <= N; j++) {
			if (j == city) continue;
			int r = findFather(j);//注意这里不是r = F[j]
			roots.insert(r);
		}
		cout << roots.size() - 1 << endl;
	}
}

1021 Deepest Root

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
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int maxn = 10010;
int N, G[maxn][maxn];
bool flag[maxn];
int big = 0;
vector<int>far;
void DFS(int root, int d) {
	if (d > big) {
		big = d;
		far.clear();
		far.push_back(root);
	}
	else if (d == big) {
		far.push_back(root);
	}
	flag[root] = true;
	for (int i = 1; i <= N; i++) {
		if (!flag[i] && G[root][i])
			DFS(i, d + 1);
	}
}
int main() {
	cin >> N;
	int a, b;
	for (int i = 1; i <= N - 1; i++) {
		cin >> a >> b;
		G[a][b] = G[b][a] = 1;
	}
	//统计联通分量
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (!flag[i]) {
			cnt++;
			DFS(i, 1);
		}
	}
	if (cnt > 1) {
		cout << "Error: " << cnt << " components\n";
		return 0;
	}
	set<int>ans;
	for (int i = 0; i < far.size(); i++) {
		ans.insert(far[i]);
	}
	far.clear();
	big = 0;
	auto p = ans.begin();
	fill(flag, flag + maxn, false);
	DFS(*p, 1);
	for (int i = 0; i < far.size(); i++) {
		ans.insert(far[i]);
	}
	for (auto p = ans.begin(); p != ans.end(); p++) {
		cout << *p << endl;
	}
}

1034 Head of a Gang

1076 Forwards on Weibo

1003 Emergency

1018 Public Bike Management

1030 Travel Plan

最短路径+结点花费最少+输出一条路径

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
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
int N, M, S, D;
int G[maxn][maxn],C[maxn][maxn];
bool flag[maxn];
int meter[maxn], cost[maxn];
int pre[maxn];
void dijkstra() {
	for (int i = 0; i < N; i++) {
		int min = INF, id = -1;
		for (int j = 0; j < N; j++) {
			if (!flag[j] && meter[j] < min) {
				min = meter[j];
				id = j;
			}
		}
		if (id == -1)return;
		flag[id] = true;
		for (int j = 0; j < N; j++) {
			if (!flag[j] && G[id][j]) {
				if (G[id][j] + meter[id] < meter[j]) {
					pre[j] = id;
					meter[j] = G[id][j] + meter[id];
					cost[j] = C[id][j] + cost[id];
				}
				else if (G[id][j] + meter[id] == meter[j]) {
					if (C[id][j] + cost[id] < cost[j]) {
						cost[j] = C[id][j] + cost[id];
						pre[j] = id;
					}
				}
			}
		}
	}
}
int main() {
	cin >> N >> M >> S >> D;
	int a, b, d, c;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> d >> c;
		G[a][b] = G[b][a] = d;
		C[a][b] = C[b][a] = c;
	}
	fill(meter, meter + maxn, INF);
	fill(cost, cost + maxn, INF);
	meter[S] = 0;
	cost[S] = 0;
	dijkstra();
	vector<int>road;
	int id = D;
	while (id!=S) {
		road.push_back(id);
		id = pre[id];
	}
	road.push_back(id);
	for (int i = road.size() - 1; i >= 0; i--) {
		cout << road[i] << " ";
	}
	cout << meter[D] << " " << cost[D];
}

1072 Gas Station

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
#include<iostream>
#include<vector>
#include<set>
#include<math.h>
using namespace std;
const int INF = 1000000000;
const int maxn = 1020;
int N, M, K, D;
int G[maxn][maxn];
set<int>station;
int meter[maxn];
bool flag[maxn];
void dijkstra(int s) {
	for (int i = 0; i < N + M; i++) {
		int min = INF, id = -1;
		for (int j = 1; j <= N + M; j++) {
			if (meter[j] < min&&!flag[j]) {
				min = meter[j];
				id = j;
			}
		}
		if (id == -1)return;
		flag[id] = true;
		if (meter[id] > D && id <= N)return;
		for (int j = 1; j <= N + M; j++) {
			if (G[id][j] && !flag[j]) {
				if (G[id][j] + meter[id] < meter[j]) {
					meter[j] = G[id][j] + meter[id];
				}
			}
		}
	}
}
int main() {
	cin >> N >> M >> K >> D;
	string s1, s2;
	int c1, c2, d;
	for (int i = 0; i < K; i++) {
		cin >> s1 >> s2 >> d;
		if (s1[0] == 'G') {
			s1 = s1.substr(1, s1.size() - 1);
			c1 = atoi(s1.c_str());
			c1 += N;
			station.insert(c1);
		}
		else c1 = atoi(s1.c_str());
		if (s2[0] == 'G') {
			s2 = s2.substr(1, s2.size() - 1);
			c2 = atoi(s2.c_str());
			c2 += N;
			station.insert(c2);
		}
		else c2 = atoi(s2.c_str());
		G[c1][c2] = G[c2][c1] = d;
	}
	double big = 0.0;
	double average = 1.0 * INF;
	int best;
	bool ans = false;
	for (auto it = station.begin(); it != station.end(); it++) {
		fill(flag, flag + maxn, false);
		fill(meter, meter + maxn, INF);
		meter[*it] = 0;
		dijkstra(*it);
		double minitemp = INF, total = 0;
		bool flag = true;
		for (int i = 1; i <= N; i++) {
			if (meter[i] > D) {
				flag = false; break;
			}
			if (meter[i] < minitemp) minitemp = meter[i];
			total += meter[i];
		}
		/*for (int i = 1; i <= N+M; i++) cout << meter[i] << " ";
		cout << endl;*/
		/*cout << "G" << *it - N << endl;
		printf("%.1f %.1f", minitemp, total / N);*/
		if (flag) {
			ans = true;
			if (big < minitemp) {
				average = total;
				best = *it;
				big = minitemp;
			}
			else if (big == minitemp && average > total) {
				average = total;
				best = *it;
			}
		}
	}
	if (ans) {
		cout << "G" << best - N << endl;
		printf("%.1f %.1f", big, average / N);//ceil(average / N * 10) / 10
	}
	else {
		cout << "No Solution";
	}
}

1087 All Roads Lead to Rome

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
#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int maxn = 210;
const int INF = 1000000000;
int N, K;
string start;
map<string, int>city;
map<int, string> name;
int happy[maxn];//每个城市的初始快乐值
int G[maxn][maxn];
bool flag[maxn];
int meter[maxn];//每个城市累计最短距离
//int hap[maxn];//每个城市累计快乐值
vector<int> pre[maxn];
void dijkstra() {
	for (int i = 0; i < N; i++) {
		int min = INF, id = -1;
		for (int j = 0; j < N; j++) {
			if (!flag[j] && meter[j]<min) {
				min = meter[j];
				id = j;
			}
		}
		if (id == -1)return;
		flag[id] = true;
		for (int j = 0; j < N; j++) {
			if (!flag[j]&&G[id][j]) {
				if (meter[id] + G[id][j] < meter[j]) {
					meter[j] = meter[id] + G[id][j];
					pre[j].clear();
					pre[j].push_back(id);
				}
				else if (meter[id] + G[id][j] == meter[j]) {
					pre[j].push_back(id);
				}
			}
		}
	}
}
vector<int>temp;
vector<int>path;
int maxhappy = 0;
double avehappy = 0;
int cnt = 0;
void DFS(int r) {
	temp.push_back(r);
	if (r == 0) {
		cnt++;
		int temphappy = 0;
		for (int i = 0; i < temp.size(); i++) {
			temphappy += happy[temp[i]];
		}
		//cout << temp.size();
		if (temphappy > maxhappy) {
			maxhappy = temphappy;
			path = temp;
			avehappy = maxhappy / (temp.size() - 1);
		}
		else if (temphappy == maxhappy && (temphappy / (temp.size()-1)) > avehappy) {
			avehappy = temphappy / (temp.size()-1);
			path = temp;
		}
		temp.pop_back();
		return;
	}
	for (int i = 0; i < pre[r].size(); i++) {
		DFS(pre[r][i]);
	}
	temp.pop_back();
}
int main() {
	cin >> N >> K >> start;
	city[start] = 0;
	name[0] = start;
	string c, c1;
	int h;
	for (int i = 1; i < N; i++) {
		cin >> c >> h;
		city[c] = i;
		name[i] = c;
		happy[i] = h;
	}
	for (int i = 0; i < K; i++) {
		cin >> c >> c1 >> h;
		G[city[c]][city[c1]] = G[city[c1]][city[c]] = h;
	}
	fill(meter, meter + maxn, INF);
	meter[0] = 0;
	dijkstra();
	DFS(city["ROM"]);
	cout << cnt << " " << meter[city["ROM"]] << " " << maxhappy << " " << avehappy << endl;
	for (int i = path.size()-1; i >=0; i--) {
		cout << name[path[i]];
		if (i != 0)cout << "->";
	}
}
 Comments