HDU 5723 – Abandoned country [Kruskal+DFS]

http://acm.hdu.edu.cn/showproblem.php?pid=5723

Problem

An abandoned country has n(n100000) villages which are numbered from 1 to n. Since abandoned for a long time, the roads need to be re-built. There are m(m1000000) roads to be re-built, the length of each road is wi(wi1000000). Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.

Mean

N个城市M个双向边，保证M条边能让所有城市联通，M条边权值各不相同。选取N-1条边让他们联通并且权值之和最小。

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;

const int maxn = 102400;
struct Edge {
int u, v, d;
bool operator < (const Edge &rhs) const {
return d < rhs.d;
}
};
int N, M;
int pa[maxn];
bool vis[maxn];
ll ans;
Edge e[maxn*10];
vector<P> G[maxn];

void init() {
for(int i = 0; i < maxn; ++i) {
pa[i] = i;
G[i].clear();
}
ans = 0;
memset(vis, false, sizeof(vis));
}

int Find(int x) {
return pa[x] == x ? x : pa[x] = Find(pa[x]);
}

ll kruskal() {
sort(e, e + M);
int cnt = 0;
ll sum = 0;
for(int i = 0; i < M; ++i) {
int rx = Find(e[i].u);
int ry = Find(e[i].v);
if(rx != ry) {
cnt += 1;
pa[rx] = ry;
sum += e[i].d;
G[e[i].u].push_back(P(e[i].v, e[i].d));
G[e[i].v].push_back(P(e[i].u, e[i].d));
}
if(cnt >= N-1)
break;
}
return sum;
}

int dfs(int u) {
vis[u] = true;
int cnt = 0;
for(P &p : G[u]) {
if(vis[p.first])
continue;
int t = dfs(p.first);
ans += (ll)p.second * (ll)t * (ll)(N-t);
cnt += t;
}
return cnt + 1;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &N, &M);
for(int i = 0; i < M; ++i) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
}
init();
ll sum = kruskal();
dfs(1);
printf("%I64d %.2f\n", sum, (double)ans * 2.0 / ((double)N * (double)(N-1)));
}
return 0;
}