🧠 题解（Solution）

✅ 本质分析

这是一个典型的最小生成树（MST）问题：

输入是一个完全图，每对村庄之间都有距离；

有若干边已提前连通；

要求在已有边的基础上，用最少代价将所有村庄连通。

✅ 解法思路

使用 Kruskal 或 Prim 算法求最小生成树：

将所有边加入边集合 $E$；

对于已建道路 $Q$，可以视为权值为 $0$ 或提前加入并查集；

对边按权值升序排序；

用**并查集（Disjoint Set Union）**处理连通性：

初始时将所有村庄视为独立集合；

对于每条边，如果两个端点不连通，就连接它们，并加上边权；

直到所有村庄在同一集合中为止。

🧮 示例分析

输入图：

村庄之间距离：

[ 0 990 692 990 0 179 692 179 0 ] ​

0 990 692 ​

990 0 179 ​

692 179 0 ​

​

已建道路 $(1, 2)$，这条边可以视为“已连通”，不计入新建成本；

要让村庄 $1$、$2$、$3$ 全部连通，只需加一条边：$(2, 3)$，代价为 $179$。

⏱ 时间复杂度 Kruskal 算法时间复杂度：$O(E \log E)$，其中 $E \leq \frac{N(N-1)}{2}$；

并查集操作近似 $O(1)$；

适用于 $N \leq 100$ 的范围。

代码实现

#include<bits/stdc++.h>
using namespace std;
int father[110];
struct Graph
{
	int u;
	int v;
	int dis;
}maps[10010];

int grid[110][110];
void init(int n)
{
	for(int i=1;i<=n;i++) father[i]=i;
}
int find(int x)
{
	while(father[x]!=x) x=father[x];
	return x;
}
void join(int a,int b)
{
	int t1=find(a);
	int t2=find(b);
	if(t1!=t2) father[t1]=t2;
}
int getNum(int n)
{
	int num = 0;
	for(int i=1;i<=n;i++)
		if(father[i]==i)
			num++;
	return num;
}
int main()
{
	int n;
	while(cin>>n)
	{
		memset(grid,0,sizeof(grid));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				cin >> grid[i][j];
		int q;
		cin >> q;
		while(q--)
		{
			int a,b;
			cin >> a >> b;
			grid[a][b] = 0;
			grid[b][a] = 0;
		}
		
		int edgeNum = 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(i==j)continue;
				maps[++edgeNum].u = i;
				maps[edgeNum].v = j;
				maps[edgeNum].dis = grid[i][j];
			}
		sort(maps+1,maps+1+edgeNum,[](Graph x,Graph y)->bool{ return x.dis<y.dis;});
		init(n);
		int distance = 0;
		for(int i=1;i<=edgeNum;i++)
		{
			if(find(maps[i].u) != find(maps[i].v))
			{
				join(maps[i].u,maps[i].v);
				distance += maps[i].dis;
			}
		}
		cout << distance << endl;
	}
	return 0;
}