最小生成树与边替换判定 - 解题思路

这段代码使用Prim算法构建最小生成树(MST)，并预处理每条非树边替换树边时的最大边权值，用于快速回答边替换查询。

算法核心思路

1. 图初始化：

   • 读取顶点数n、边数m和查询数q
   • 构建图的邻接矩阵表示，初始化所有边权为无穷大
   • 添加实际边信息到邻接矩阵

2. Prim算法构建MST：

   • 从顶点1开始构建最小生成树
   • 维护两个数组：
     • cost[]：记录各顶点到当前MST的最小边权
     • pre[]：记录各顶点在MST中的前驱顶点
   • 同时计算并存储dp[u][v]，表示在MST中u到v路径上的最大边权

3. 查询处理：

   • 对于每个查询，检查给定边(x)的权值weight是否小于等于MST中对应路径的最大边权
   • 如果是，则可以用该边替换MST中的某条边（输出"Yes"）
   • 否则不能替换（输出"No"）

关键算法特性

• Prim算法：采用贪心策略逐步构建MST，时间复杂度O(n²)
• 动态规划预处理：在构建MST的同时计算任意两点间路径的最大边权
• 高效查询：预处理后每个查询可在O(1)时间内完成
• 应用场景：适用于需要频繁判断边是否可替换MST边的场景

该算法能高效处理最小生成树相关的动态查询问题，特别适合需要多次判断边替换可行性的应用。

#include <cstdio>
#include <cstring>
#include <algorithm> 
using namespace std;
const int MAX = 1005;
const int INF = 0x3f3f3f3f;
bool vis[MAX];
int pre[MAX];
int cost[MAX];
int map[MAX][MAX];
int dp[MAX][MAX];
int n,m,q;
struct Node{
	int u;
	int v;
	int w;
}edge[100000+10];
 
void init()//初始化 
{
	int i;
	for(i=1;i<=n;i++){
		cost[i] = map[1][i];
		pre[i] = 1;
	}
	memset(dp,0,sizeof(dp));
	memset(vis,false,sizeof(vis));
}
 
void add_edge(int u,int v,int w){   //构造图 
	if(w < map[u][v]){
		map[u][v] = map[v][u] = w;
	}
}
 
void Prim()
{
	init();
	vis[1] = true;
	//int sum = 0;
	while(1)
	{
		int u = -1,i,min = INF,v;
		for(i=1;i<=n;i++){
			if(!vis[i] && min>cost[i]){
				min = cost[i];
				u = i;
			}
		}
		vis[u] = true;
		if(u==-1){
			break;
		}
		//sum += cost[u];
		for(v=1;v<=n;v++){
			if(vis[v] && v!=u){   // 点u加入到生成树集合里,它与谁相连, 删(u,v)环路中 ，除了边(u,v)外的最大边
				dp[u][v] = dp[v][u] = max(dp[v][pre[u]],cost[u]); //u为即将要加入的点，而v是已经在生成树顶点集合里的点。
			}
			if(!vis[v] && cost[v]>map[u][v]){
				cost[v] = map[u][v];
				pre[v] = u;  //记录路径  v的前驱是u; 
			}
		}
	} 
}
int main()
{
	while(scanf("%d%d%d",&n,&m,&q)!=EOF){
		int i,j;
		memset(map,0x3f,sizeof(map));
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
			add_edge(edge[i].u,edge[i].v,edge[i].w); 
		} 
		Prim();
		int x,weight;
		while(q--)
		{
			scanf("%d%d",&x,&weight);
			if(dp[edge[x].u][edge[x].v]>=weight){
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}
	}
	return 0;
}