本文主要是介绍POJ 2421 Constructing Roads （MST），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题中给了n*n的矩阵，值是i点到j点的建边的花费，其中已经建好了m条边，题中求还需要花费多少才能使该图连通
思路：Kruskal更好做（并查集）。初始化之后，将m条边依次加入并查集，只要能合并及时合并。
/************************************************ Author: fisty* Created Time: 2015/2/28 14:04:54* File Name : D.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define MAX_N 10010
int n;
int cnt;
struct edge{int u;int v;int cost;
}G[MAX_N];void addedge(int u, int v, int cost){G[cnt].u = u;G[cnt].v = v;G[cnt].cost = cost;cnt++;
}
bool cmp(edge e1, edge e2){return e1.cost < e2.cost;
}
int par[MAX_N];
void init(){for(int i = 0;i <= n; i++){par[i] = i;}
}
int find(int x){if(x == par[x]) return x;return par[x] = find(par[x]);
}
void unio(int x, int y){x = find(x);y = find(y);if(x != y){par[x] = y;}
}
int kurskal(){sort(G, G + cnt, cmp);int ans = 0;for(int i = 0;i < cnt; i++){edge e = G[i];if(find(e.u) != find(e.v)){unio(e.u, e.v);ans += e.cost;}}return ans;
}int main() {//freopen("in.cpp", "r", stdin);cin.tie(0);ios::sync_with_stdio(false);cin >> n;cnt = 0;FOR(i, 1, n+1){FOR(j, 1, n+1){int cost;cin >> cost;if(i != j)addedge(i, j, cost);}}init();int Q;cin >> Q;FOR(i, 0, Q){int u, v;cin >> u >> v;unio(u, v);}int ans = kurskal();cout << ans << endl;return 0;
}
这篇关于POJ 2421 Constructing Roads （MST）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
