题解 | 继续畅通工程（Kruskal+并查集）
继续畅通工程
https://www.nowcoder.com/practice/16212f7d46e44174b5505997ea998538
一、注意事项：
- 预备数据结构：
vector<Edge> edges;存储尚未修建的路（边）edge_cnt：计算已修建的边数目。- 已修建的路可以不加入 edges 中。
- edge_cnt：
- 注意：从输入时就开始计算，并且只有加入该边不形成环时才
edge_cnt++; - 本人错因：未判断是否成环就++了。（即第55行代码 需要判断
same(s,t))
二、代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int num = 101;
vector<int> father(num);
void init() {
for(int i = 0; i<num; i++) father[i] = i;
}
int find(int u) {
if(u==father[u]) return u;
else return father[u] = find(father[u]);
}
bool same(int u, int v) {
u = find(u);
v = find(v);
if(u==v) return true;
else return false;
}
void join(int u, int v) {
u = find(u);
v = find(v);
if(u==v) return;
else father[v] = u;
}
struct Edge{
int s;
int t;
int v;
Edge(){}
Edge(int n1, int n2, int n3):s(n1),t(n2),v(n3){}
};
bool myCmp(Edge& e1, Edge& e2) {
return e1.v<e2.v;
}
int main() {
int n;
while (cin >> n) { // 注意 while 处理多个 case
if(n==0) break;
init();
int s,t,val,build;
vector<Edge> edges;
int cost = 0;
int edge_cnt = 0;
for(int i = 0; i<n*(n-1)/2; i++) {
cin>>s >> t >> val >> build;
if(build==1 && !same(s,t)) {
edge_cnt++;
join(s, t);
// cost += val;
continue;
}
edges.push_back(Edge(s,t,val));
}
sort(edges.begin(), edges.end(), myCmp);
// for(int i = 0; i<edges.size(); i++) {
// cout << ":: " << edges[i].s << "->" << edges[i].t << "(" << edges[i].v << ")" << endl;
// }
while(edge_cnt<n-1) {
for(int i = 0; i<edges.size(); i++) {
if(same(edges[i].s, edges[i].t)) continue;
else {
cost+=edges[i].v;
join(edges[i].s, edges[i].t);
edge_cnt++;
break;
}
}
}
cout << cost << endl;
}
}
// 64 位输出请用 printf("%lld")
