HDU1233 还是畅通工程【最小生成树】

2019-11-06 06:27:21

字体：大中小

来源：转载

供稿：网友

PRoblem: 给定每两节点间的距离，求出这幅图的最小生成树的权值。 Solution: 利用kruskal或者prim算法求最小生成树，密集图prim算法的效率会更高一些。

kruskal:

#include<numeric>#include<functional>#include<unordered_map>#include<unordered_set>#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<ctime>#include<vector>#include<fstream>#include<list>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;int par[110];void init_pair(int n) { for(int i = 0; i <= n; i++) par[i] = i;}int find(int son) { if(par[son] != son) par[son] = find(par[son]); return par[son];}void merges(int a, int b) { par[find(a)] = par[b];}struct Edge { int b, e, w; Edge(int bb, int ee, int ww) : b(bb), e(ee), w(ww) {} bool Operator < (const Edge& rhs) const { return w > rhs.w; }};priority_queue<Edge> pq;int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int n; int a, b, c, ans; while(cin >> n) { if(n == 0) break; init_pair(n); while(!pq.empty()) pq.pop(); ans = 0; for(int i = 0; i < n*(n-1)/2; i++) { cin >> a >> b >> c; pq.push(Edge(a, b, c)); } while(!pq.empty()) { Edge t = pq.top(); pq.pop(); if(find(t.b) != find(t.e)) { merges(t.b, t.e); ans += t.w; } } cout << ans << endl; } return 0;}

Prim

#include<numeric>#include<functional>#include<unordered_map>#include<unordered_set>#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<ctime>#include<vector>#include<fstream>#include<list>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;int G[105][105];int visited[110];int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int n, ans; int a, b, c, mins, idx; while(cin >> n) { if(n == 0) break; ms(visited); visited[1] = true; ans = 0; for(int i = 0; i < n*(n-1)/2; i++) { cin >> a >> b >> c; G[a][b] = G[b][a] = c; } for(int i = 2; i <= n; i++) { mins = INF; for(int j = 1; j <= n; j++) { if(!visited[j] && G[1][j] < mins) { mins = G[1][j]; idx = j; } } visited[idx] = true; ans += mins; for(int j = 1; j <= n; j++) G[1][j] = min(G[1][j], G[idx][j]); } cout << ans << endl; } return 0;}

上一篇：动态库与静态库优缺点比较

下一篇：DSP调试通过，可以运行，观测变量数据为-1.#QNAN的原因