题目详情提交记录（0）

详细题解？

userId_undefined

AC是最好的

秩序白银

2025-10-12 21:28:12

发布于：福建

31阅读
0回复
0点赞

  • 题目大意

给定了一个 nn 个定点 mm 条边的无向图，找出满足条件的四个景点
输出四个景点的分数和最大值

  • 思路1：

按照题目说法，两个点的距离不超过k+1，且四个点不同
可以先跑多源最短路，然后枚举四个景区，找出符合条件中的分数和的最大值
时间复杂度：O(n4)O(n^4)

  • 解法1

bfs/floyd求多远最短路+暴力枚举四个景点：时间复杂度---> O(n4)O(n^4)-ACGO：0分，洛谷：55分

只有bfs

#include <bits/stdc++.h>

using namespace std;

#define int long long
const long long N = 3e3 + 10;
const long long M = 1e4 + 10;
#define INF 0x3f3f3f3f
long long n , m , k;
long long score[N];//点权
long long g[N][N];//邻接矩阵
long long min_dis[N][N];//最短路数组
long long vis[N];//标记数组


struct point {
	long long to;//某个点的标号
	long long step;//起点到to点的最短距离
};

//bfs求单元最短路
void bfs(point s) {
	queue<point> q;
	//广搜第一步：起点入队+标记
	q.push(s);
	vis[s . to] = 1;
	
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		//广搜第二步:找邻接点
		for (int i = 1 ; i <= n ; i++) {
			if (g[p.to][i] != INF && !vis[i]) {
				//广搜第三步:入队继续广搜
				q.push({i , p.step + 1});
				min_dis[s.to][i] = p.step + 1;
				vis[i] = 1;
			}
		}
	}
}

signed main( ) {
	cin >> n >> m >> k;
	
	for (int i = 2 ; i <= n ; i++) {
		scanf("%lld" , &score[i]);//读入点权
	}
	
	fill(g[0] , g[0] + N * N , INF);//默认所有点不通
	fill(min_dis[0] , min_dis[0] + N * N , INF);//初始化为极大值
	//建图
	for (int i = 1 ; i <= m ; i++) {
		long long u , v;
		scanf("%lld%lld" , &u , &v);
		g[u][v] = g[v][u] = 1;//无权图
		min_dis[u][v] = min_dis[v][u] = 1;
	}
	
	//bfs求多源最短路
	for (int i = 1 ; i <= n ; i++) {
		memset(vis , 0 , sizeof vis);
		bfs({i , 0});
	}
	
	//Floyd求多源最短路
	//floyd();
	k++;
	long long ans = 0;
	//枚举四个景点(四个景点不通，两两距离不超过k+1)
	for (int i = 1 ; i <= n ; i++) {
		if (min_dis[1][i] <= k) {
			for (int j = 1 ; j <= n ; j++) {
				if (j != i && min_dis[i][j] < k) {
					for (int p = 1 ; p <= n ; p++) {
						if (p != i && p != j && min_dis[j][p]  <= k) {
							for (int q = 1 ; q <= n ; q++) {
								if (q != p && q != j && q != i && min_dis[p][q] <= k && min_dis[q][1] <= k) {
									ans = max(ans , score[i] + score[j] + score[p] + score[q]);
								}
							}
						}
					}
				} 
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

floyd+bfs

#include <bits/stdc++.h>

using namespace std;

#define int long long
const long long N = 3e3 + 10;
const long long M = 1e4 + 10;
#define INF 0x3f3f3f3f
long long n , m , k;
long long score[N];//点权
long long g[N][N];//邻接矩阵
long long min_dis[N][N];//最短路数组
long long vis[N];//标记数组


struct point {
	long long to;//某个点的标号
	long long step;//起点到to点的最短距离
};

//bfs求单元最短路
void bfs(point s) {
	queue<point> q;
	//广搜第一步：起点入队+标记
	q.push(s);
	vis[s . to] = 1;
	
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		//广搜第二步:找邻接点
		for (int i = 1 ; i <= n ; i++) {
			if (g[p.to][i] != INF && !vis[i]) {
				//广搜第三步:入队继续广搜
				q.push({i , p.step + 1});
				min_dis[s.to][i] = p.step + 1;
				vis[i] = 1;
			}
		}
	}
}

//floyd求多源最短路
void floyd() {
	for (int k = 1 ; k <= n ; k++) {
		for (int i = 1 ; i <= n ; i++) {
			for (int j = 1 ; j <= n ; j++) {
				if (min_dis[i][j] >= min_dis[i][k] + min_dis[k][j]) {
					min_dis[i][j] = min_dis[i][k] + min_dis[k][j];
				}
			}
		}
	}
}

signed main( ) {
	cin >> n >> m >> k;
	
	for (int i = 2 ; i <= n ; i++) {
		scanf("%lld" , &score[i]);//读入点权
	}
	
	fill(g[0] , g[0] + N * N , INF);//默认所有点不通
	fill(min_dis[0] , min_dis[0] + N * N , INF);//初始化为极大值
	//建图
	for (int i = 1 ; i <= m ; i++) {
		long long u , v;
		scanf("%lld%lld" , &u , &v);
		g[u][v] = g[v][u] = 1;//无权图
		min_dis[u][v] = min_dis[v][u] = 1;
	}
	
	//bfs求多源最短路
	/*for (int i = 1 ; i <= n ; i++) {
		memset(vis , 0 , sizeof vis);
		bfs({i , 0});
	}*/
	
	//Floyd求多源最短路
	floyd();
	k++;
	long long ans = 0;
	//枚举四个景点(四个景点不通，两两距离不超过k+1)
	for (int i = 1 ; i <= n ; i++) {//枚举景点a
		if (min_dis[1][i] <= k) {
			for (int j = 1 ; j <= n ; j++) {//枚举景点b
				if (j != i && min_dis[i][j] <= k) {
					for (int p = 1 ; p <= n ; p++) {
						if (p != i && p != j && min_dis[j][p]  <= k) {
							for (int q = 1 ; q <= n ; q++) {
								if (q != p && q != j && q != i && min_dis[p][q] <= k && min_dis[q][1] <= k) {
									ans = max(ans , score[i] + score[j] + score[p] + score[q]);
								}
							}
						}
					}
				} 
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

  • 思路2

在解法1的基础上，考虑景点a，d，这两个点世比较特殊的，a和d一定是家的邻点
并且a和d和家的距离 ≤\leq k+1的，所以我们可以优先处理最优候选点a,d
后续我们只需要枚举b和d之后再去最优候选点中查找a和d即可

  • 解法2

bfs求多源最短路+枚举优化------>时间复杂度：O(n2)O(n^2)-100pts

0pts代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
const long long N = 3e3 + 10;
const long long M = 1e4 + 10;
#define INF 0x3f3f3f3f
long long n , m , k;
long long w[N];//点权
long long min_dis[N][N];//最短路数组
long long vis[N];//标记数组
vector<long long> g[N];//邻接表存图

//快写
inline long long read( ) {
	long long w = 0;
	long long s = 1;
	char c= getchar();
	while(c < '0' || c > '9') {
		if (c == '-') {
			s = -1;
			c = getchar();
		}
	}
	
	while(c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	
	return s * w;
}

struct point {
	long long v;//某个点的标号
	long long step;//起点到to点的最短距离
};
set<pair<int , int>> s[N];//维护a和d的最有候选点

//bfs求单元最短路
void bfs(point s) {
	queue<point> q;
	//广搜第一步：起点入队+标记
	q.push(s);
	vis[s.v] = 1;
	
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		//广搜第二步:找邻接点
		for (int i = 1 ; i <= n ; i++) {
			if (g[p.v][i] != INF && !vis[i]) {
				//广搜第三步:入队继续广搜
				q.push({i , p.step + 1});
				min_dis[s.v][i] = p.step + 1;
				vis[i] = 1;
			}
		}
	}
}


signed main( ) {
	n = read();
	m = read();
	k = read();
	
	for (int i = 2 ; i <= n ; i++) {
		w[i] = read();
	}
	fill(min_dis[0] , min_dis[0] + N * N , INF);
	for (int i = 1 ; i <= m ; i++) {
		long long u , v;
		u = read();
		v = read();
		g[u].push_back(v);
		g[v].push_back(u);//邻接表建图
		min_dis[u][v] = min_dis[v][u] = 1;
	}
	
	for (int i = 1 ; i <= n ; i++) {
		min_dis[i][i] = 0;
	}
	
	//bfs求多源最短路
	for (int i = 1 ; i <= n ; i++) {
		memset(vis , 0 , sizeof vis);
		bfs({i , 0});
	}
	
	k++;
	//预处理a,d的最佳候选点j
	for (int i = 2 ; i <= n ; i++) {
		for (int j = 2 ; j <= n ; j++) {
			if(i == j) continue;
			if (min_dis[i][j] <= k && min_dis[1][j] <= k) {
				s[i].insert({w[j] , j});
			}
			if (s[i].size() > 3) {
				s[i].erase(s[i].begin());//维护前三大
			}
		}
	}
	
	long long ans = 0;
	
	for (int b = 2 ; b <= n ; b++) {
		for (int c = 2 ; c <= n ; c++) {
			if (b == c || min_dis[b][c] > k) {
				continue;
			}
			for (auto a : s[b]) {
				if (a.second == b || a.second == c) {
					continue;
				}
				for (auto d : s[c]) {
					if (d.second == b || d.second == c || d.second == a.second) {
						continue;
					}
					ans = max(ans , w[a.second] + w[b] + w[c] + w[d.second]);
				}
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

错误点原因：因为100pts的解法是邻接表，很多人会把暴力代码（解法1）的遍历方法复制过来导致错误

正确代码（100pts）

#include <bits/stdc++.h>

using namespace std;

#define int long long
const long long N = 3e3 + 10;
const long long M = 1e4 + 10;
#define INF 0x3f3f3f3f
long long n , m , k;
long long w[N];//点权
long long min_dis[N][N];//最短路数组
long long vis[N];//标记数组
vector<long long> g[N];//邻接表存图

//快写
inline long long read( ) {
	long long w = 0;
	long long s = 1;
	char c= getchar();
	while(c < '0' || c > '9') {
		if (c == '-') {
			s = -1;
			c = getchar();
		}
	}
	
	while(c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	
	return s * w;
}

struct point {
	long long v;//某个点的标号
	long long step;//起点到to点的最短距离
};
set<pair<int , int>> s[N];//维护a和d的最有候选点

//bfs求单元最短路
void bfs(point s) {
	queue<point> q;
	//广搜第一步：起点入队+标记
	q.push(s);
	vis[s.v] = 1;
	
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		//广搜第二步:找邻接点
		for (int i = 0 ; i < g[p.v].size() ; i++) {
			long long u = g[p.v][i];
			if (!vis[u]) {
				q.push({u , p.step + 1});
				min_dis[s.v][u] = p.step + 1;
				vis[u] = 1;
			}
		}
	}
}


signed main( ) {
	n = read();
	m = read();
	k = read();
	
	for (int i = 2 ; i <= n ; i++) {
		w[i] = read();
	}
	fill(min_dis[0] , min_dis[0] + N * N , INF);
	for (int i = 1 ; i <= m ; i++) {
		long long u , v;
		u = read();
		v = read();
		g[u].push_back(v);
		g[v].push_back(u);//邻接表建图
		min_dis[u][v] = min_dis[v][u] = 1;
	}
	
	for (int i = 1 ; i <= n ; i++) {
		min_dis[i][i] = 0;
	}
	
	//bfs求多源最短路
	for (int i = 1 ; i <= n ; i++) {
		memset(vis , 0 , sizeof vis);
		bfs({i , 0});
	}
	
	k++;
	//预处理a,d的最佳候选点j
	for (int i = 2 ; i <= n ; i++) {
		for (int j = 2 ; j <= n ; j++) {
			if(i == j) continue;
			if (min_dis[i][j] <= k && min_dis[1][j] <= k) {
				s[i].insert({w[j] , j});
			}
			if (s[i].size() > 3) {
				s[i].erase(s[i].begin());//维护前三大
			}
		}
	}
	
	long long ans = 0;
	
	for (int b = 2 ; b <= n ; b++) {
		for (int c = 2 ; c <= n ; c++) {
			if (b == c || min_dis[b][c] > k) {
				continue;
			}
			for (auto a : s[b]) {
				if (a.second == b || a.second == c) {
					continue;
				}
				for (auto d : s[c]) {
					if (d.second == b || d.second == c || d.second == a.second) {
						continue;
					}
					ans = max(ans , w[a.second] + w[b] + w[c] + w[d.second]);
				}
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

看在作者这么努力的份上，给个赞吧求求了……

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

暂无数据

提交答案之后，这里将显示提交结果～

首页