HDU 5723 – Abandoned country [Kruskal+DFS]

Link

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条边让他们联通并且权值之和最小。

然后计算任意两城市之间最短距离的期望。

Analysis

题意比较明显,先求最小生成树,由于每条边长度不同,因此最小生成树是唯一的。求的过程中建树。最后选任意根结点dfs一遍即可,统计每条边的子节点个数t,当前边经过的次数就是t*(t-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;
}

欢迎留言