题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5723
题意:求最小生成树,并且求这棵最小生成树上所有边走过次数的期望。
走过次数的期望=Σ边被走过次数*边权/(n*(n-1)/2)
求边被走过的次数,相当于关心这个边的两侧分别有多少点,走的次数就是两边的点数的乘积这个很好理解。可以从边的一侧开始dfs,找到这个边的一侧点数x,由于最小生成树是联通的,那么边的另一侧点数一定是n-x。所以这条边的贡献是(n-x)*x*w。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
typedef struct Edge {
int v, next;
LL w;
}Edge; typedef struct E {
int u, v;
LL w;
}E;
const int maxn = ;
const int maxm = ;
int n, m;
E e[maxm<<];
Edge edge[maxm<<];
int head[maxn], ecnt;
int pre[maxn];
LL ret1, ret2; int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
} bool unite(int x, int y) {
x = find(x); y = find(y);
if(x != y) {
pre[x] = y;
return ;
}
return ;
} void init() {
memset(head, -, sizeof(head));
ecnt = ; ret1 = ; ret2 = ;
for(int i = ; i <= n; i++) pre[i] = i;
} void adde(int u, int v, LL w) {
edge[ecnt].v = v; edge[ecnt].w = w; edge[ecnt].next = head[u]; head[u] = ecnt++;
edge[ecnt].v = u; edge[ecnt].w = w; edge[ecnt].next = head[v]; head[v] = ecnt++;
} bool cmp(E a, E b) {
return a.w < b.w;
} int dfs(int u, int p) {
int siz = ;
for(int i = head[u]; ~i; i=edge[i].next) {
int v = edge[i].v; LL w = edge[i].w;
if(p == v) continue;
int pre = dfs(v, u);
siz += pre;
ret2 += (LL)pre * (LL)(n - pre) * w;
}
return siz;
} int main() {
//freopen("in", "r", stdin);
int T, u, v;
LL w;
scanf("%d", &T);
while(T--) {
scanf("%d%d",&n,&m);
init();
for(int i = ; i < m; i++) {
scanf("%d%d%lld",&u,&v,&w);
e[i].u = u; e[i].v = v; e[i].w = w;
}
sort(e, e+m, cmp);
for(int i = ; i < m; i++) {
u = e[i].u; v = e[i].v; w = e[i].w;
if(unite(u, v)) {
ret1 += w;
adde(u, v, w);
}
}
dfs(, -);
LL k = n * (n - );
printf("%lld %.2lf\n", ret1, 2.0*ret2/(double)k);
}
return ;
}