GPLT团体程序设计天梯赛分类练习4：图

摘要

L2-3 深入虎穴 - 团体程序设计天梯赛练习4：图：BFS求树的深度

L2-4 网红点打卡攻略 - 团体程序设计天梯赛练习4：图：哈密顿回路

7-6 哲哲打游戏 - 团体程序设计天梯赛练习4：图：模拟

7-8 龙龙送外卖 - 团体程序设计天梯赛练习4：图：树

7-9 大众情人 - 团体程序设计天梯赛练习4：图：弗洛伊德求最短路

L2-3 深入虎穴

使用BFS求出树的最大深度，同时记录一下该深度下的节点。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;

vector<int > e[maxn];
bool vis[maxn];
int n,ans,max_dep;

void bfs(int x){
	queue<pair<int,int > > q;
	q.push({x, 1});
	while(!q.empty()){
		int f = q.front().first;
		int d = q.front().second;
		q.pop();
		if(d > max_dep){
			ans = f;
			d = max_dep;
		}
		for(auto it : e[f]){
			q.push({it, d+1});
		}
	}
}

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		int k;cin>>k;
		for(int j = 1 ; j <= k ; j ++){
			int s;cin>>s;
			e[i].push_back(s);
			vis[s] = true;
		}
	}
	int r = 1;
	for(int i = 1 ; i <= n ; i ++){
		if(!vis[i]){
			r = i; break;
		}
	}
	bfs(r);
	cout<<ans;
	return 0;
}

L2-4 网红点打卡攻略

给一个N节点，M条边的无向图。

对K条通路进行判断，求出其中最短的哈密顿回路。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
const int inf = 0x3f3f3f3f;

int n,m,k;
int e[maxn][maxn];
int min_,cnt,ans;

bool judge(vector<int > v){
	if((int)v.size() != n) return false;
	bool vis[maxn];
	memset(vis,false,sizeof(vis));
	vis[0] = true;
	int last = 0;
	for(auto it : v){
		if(vis[it] || e[last][it] == inf) return false;
		vis[it] = true;
		last = it;
	}
	if(e[v.back()][0] == inf) return false;
	return true;
}

int get_sum(vector<int> v){
	int res = 0;
	int last = 0;
	for(auto it : v){
		res += e[last][it];
		last = it;
	}
	res += e[v.back()][0];
	return res;
} 

int main(void){
	cin>>n>>m;
	memset(e,inf,sizeof(e));
	for(int i = 1 ; i <= m ; i ++){
		int a,b,w; cin>>a>>b>>w;
		e[a][b] = e[b][a] = w;
	}
	min_ = inf;
	cin>>k;
	for(int i = 1 ; i <= k ; i ++){
		vector<int > v;
		int t;cin>>t;
		for(int j = 1 ; j <= t ; j ++){
			int x;cin>>x;
			v.push_back(x);
		}
		if(judge(v)){
			cnt++;
			int sum = get_sum(v);
			if(sum < min_){
				min_ = sum;
				ans = i;
			}
		}
	}
	cout<<cnt<<"\n";
	cout<<ans<<" "<<min_<<"\n";
	return 0;
}

7-6 哲哲打游戏

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;

int n,m;
vector<int> nex[maxn];
int back[maxn];

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		int k;cin>>k;
		nex[i].push_back(0);
		for(int j = 1 ; j <= k ; j ++){
			int x; cin>>x;
			nex[i].push_back(x);
		}
	}
	int now = 1;
	while(m--){
		int op;
		cin>>op;
		if(op == 0){
			int to;cin>>to;
			now = nex[now][to];
		}else if(op == 1){
			int f;cin>>f;
			back[f] = now;
			cout<<now<<"\n";
		}else{
			int f;cin>>f;
			now = back[f];
		}
	}
	cout<<now;
	return 0;
}

7-8 龙龙送外卖

首先，使用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
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;

int n,r,m,ans;
int fa[maxn],dep[maxn],max_dist;
bool vis[maxn];
vector<int > e[maxn];

void dfs(int x, int d){
	dep[x] = d;
	for(auto it : e[x]){
		dfs(it, d+1);
	}
}

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		int f;cin>>f;
		if(f == -1) r = i;
		else{
			fa[i] = f;
			e[f].push_back(i);
		} 
	}
	dfs(r, 0);
	while(m--){
		int x;cin>>x;
		max_dist = max(dep[x],max_dist);
		while(!vis[x] && x != r){
			ans += 2;
			vis[x] = true;
			x = fa[x];
		}
		cout<<ans - max_dist<<"\n";
	}
	return 0;
}

7-9 大众情人

给一张有向带权图，求每个点之间的最短距离。

每个人的异性缘是离自己最远的异性（从异性走到自己）的倒数。

求出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
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
const int inf = 0x3f3f3f3f;

int n;
bool g[maxn];
int e[maxn][maxn],min_1,min_2;
vector<int > ans_1,ans_2;

void floyd(){
	for(int k = 1 ; k <= n ; k ++){
		for(int i = 1 ; i <= n ; i ++){
			if(e[i][k] == inf) continue;
			for(int j = 1 ; j <= n ; j ++){
				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
			}
		}
	}
}

int main(void){
	memset(e,inf,sizeof(e));
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		char c;cin>>c;
		g[i] = (c == 'M');
		int k;cin>>k;
		while(k--){
			int x,d; scanf("%d:%d", &x, &d);
			e[i][x] = d;
		}
	}
	min_1 = min_2 = inf;
	floyd();
	for(int i = 1 ; i <= n ; i ++){
		int d = 0;
		for(int j = 1 ; j <= n ; j ++){
			if(g[i] != g[j]){
				d = max(e[j][i], d);
			}
		}
		if(!g[i] && d < min_1){
			min_1 = d;
			ans_1.clear();
			ans_1.push_back(i);
		}else if(!g[i] && d == min_1){
			ans_1.push_back(i);
		}
		if(g[i] && d < min_2){
			min_2 = d;
			ans_2.clear();
			ans_2.push_back(i);
		}else if(g[i] && d == min_2){
			ans_2.push_back(i);
		}
	}
	if(!ans_1.empty()) cout<<ans_1.front();
	for(int i = 1 ; i < ans_1.size() ; i ++){
		cout<<" "<<ans_1[i];
	}
	cout<<"\n";
	if(!ans_2.empty()) cout<<ans_2.front();
	for(int i = 1 ; i < ans_2.size() ; i ++){
		cout<<" "<<ans_2[i];
	}
	cout<<"\n";
	return 0;
}
题解 > GPLT > 分类练习
#图论 #GPLT
GPLT团体程序设计天梯赛分类练习4：图
https://czwcugb.github.io/题解/GPLT/GPLT-Graph/
作者
ChenZhiwei
发布于
2025年3月6日
许可协议