06-3. 公路村村通（30）

本文主要是介绍06-3. 公路村村通（30），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

06-3. 公路村村通（30）

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式说明：

输入数据包括城镇数目正整数N（<=1000）和候选道路数目M（<=3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式说明：

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出-1，表示需要建设更多公路。

思路:

一个裸的最小生成树算法，最后需要判断一下是否所有顶点都连通

/************************************************ Author: fisty* Created Time: 2015/1/19 22:52:56* File Name   : 06-3.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define MAX_N 3010
int n,m;
int _rank[MAX_N],par[MAX_N];struct edge{int u;int v;int cost;edge(int _u = 0, int _v = 0, int _cost = 0):u(_u), v(_v), cost(_cost){}
}G[MAX_N];bool cmp(const edge a,const edge b){return a.cost < b.cost;
}//并查集建立
void init(int n){for(int i = 1;i <= n; i++){par[i] = i;   _rank[i] = 0;}
}
int find(int x){if(par[x] == x)return x;return par[x] = find(par[x]);
}void unit(int x, int y){x = find(x);y = find(y);if(x == y) return ;if(_rank[x] < _rank[y]){par[x] = y;}else{par[y] = x;if(_rank[x] == _rank[y]){_rank[x]++;}}
}
//最小树算法
int kruskal(){sort(G, G + m, cmp);int res = 0;for(int i = 0;i < m; i++){edge e = G[i];if(find(e.v) != find(e.u)){unit(e.u, e.v);res += e.cost;}}return res;
}
int main(){//freopen("in.txt", "r", stdin);cin.tie(0);ios::sync_with_stdio(false);cin >> n >> m;      init(n);for(int i = 0;i < m; i++){cin >> G[i].u >> G[i].v >> G[i].cost;}int ans = kruskal();//检查是否可以连通所有结点int ok = 1;for(int i = 1;i <= n;i++){for(int j = i+1; j <= n; j++){if(find(i) != find(j)){ok = 0;break;}}}if(ok)//可以连通cout << ans << endl;else//不足以连通cout << "-1" << endl;return 0;
}

这篇关于06-3. 公路村村通（30）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---