代碼：

include

include

include

using namespace std;

struct Edge {
int u, v, weight;
// 重載小于運(yùn)算符，用于邊的排序
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};

// 并查集查找函數(shù)，帶路徑壓縮
int find(vector& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}

// 并查集合并函數(shù)
void unionSets(vector& parent, int x, int y) {
parent[find(parent, x)] = find(parent, y);
}

int main() {
int n;
cin >> n;

vector<Edge> edges;

// 讀取村莊間距離并構(gòu)建邊
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        int dist;
        cin >> dist;
        if (i < j) {  // 避免重復(fù)添加邊
            edges.push_back({i, j, dist});
        }
    }
}

// 按邊的權(quán)重排序
sort(edges.begin(), edges.end());

// 初始化并查集
vector<int> parent(n + 1);
for (int i = 1; i <= n; i++) {
    parent[i] = i;
}

int q;
cin >> q;

// 處理已有道路
for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    unionSets(parent, a, b);
}

int totalLength = 0;
int edgesAdded = 0;

// 構(gòu)建最小生成樹(shù)
for (const Edge& edge : edges) {
    int rootU = find(parent, edge.u);
    int rootV = find(parent, edge.v);
    
    if (rootU != rootV) {
        unionSets(parent, rootU, rootV);
        totalLength += edge.weight;
        edgesAdded++;
        
        if (edgesAdded == n - 1) {
            break;
        }
    }
}

cout << totalLength << endl;

return 0;

}
1首先要定義數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
cpp
運(yùn)行
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};

Edge 結(jié)構(gòu)體表示圖中的一條邊，包含兩個(gè)端點(diǎn) u 和 v，以及邊的權(quán)重 weight
重載 < 運(yùn)算符用于后續(xù)邊的排序，按權(quán)重升序排列
2查并函數(shù)定義
并查集（Union-Find）實(shí)現(xiàn)
cpp
運(yùn)行
int find(vector& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}

void unionSets(vector& parent, int x, int y) {
parent[find(parent, x)] = find(parent, y);
}

并查集是處理不相交集合合并與查詢(xún)問(wèn)題的高效數(shù)據(jù)結(jié)構(gòu)
find 函數(shù)實(shí)現(xiàn)路徑壓縮，查找元素所在集合的根節(jié)點(diǎn)
unionSets 函數(shù)合并兩個(gè)集合，將一個(gè)集合的根節(jié)點(diǎn)指向另一個(gè)集合的根節(jié)點(diǎn)
3核心：
int totalLength = 0;
int edgesAdded = 0;

for (const Edge& edge : edges) {
int rootU = find(parent, edge.u);
int rootV = find(parent, edge.v);

if (rootU != rootV) {
    unionSets(parent, rootU, rootV);
    totalLength += edge.weight;
    edgesAdded++;
    
    if (edgesAdded == n - 1) {
        break;
    }
}

}