MYF

HDU 5723 Abandoned country

Posted on | In | | Visitors

题目链接

HDU 5723

解题方法：prim+heap + DFS

题目分析

题目大意

一个国王在一个图中新建一个最小生成树，然后算任意两个不同点之间距离的期望。

解析

最小生成树不难生成，使用prim即可，但是第一发交上去就t了，所以采用了prim+heap进行优化，结果还是T了，我不禁深深的陷入了沉思，神奇的是，第二天相同的代码就变成了wa了。

言归正传，大概分为两步走，第一步先建立最小生成树，第二步算距离的期望。任选一条边可以发现一个规律，经过该边的次数是两个端点作为根节点行程的子数元素数的乘积。

了解了这个规律之后，新建出来的树跑一遍DFS，处理出所有节点所领导的子数的元素数量，然后相加除以总情况的数量即可。

注意数据范围！

注意数据范围！

注意数据范围！

正好今天也总结一下各个类型变量的数据范围：

类型 数据范围 计数法表示
int -2147483648～2147483647 -2*109~2*109
long long 9223372036854775807~-9223372036854775808 -9 *1018~9*1018
double   10308
0x3f3f3f3f 1061109567 109

代码

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
typedef long long mytype;
#define Vmax 100005
#define Emax 1000005;
struct Edge{
    int v,next;
    int length;
}e[2*1000005];
ll weight;
int he[Vmax],ecnt,n,m;
int dis[Vmax],vis[Vmax],pre[Vmax],son[Vmax];
void adde(int u ,int v, int w){
    e[ecnt].v=v;
    e[ecnt].length=w;
    e[ecnt].next=he[u];
    he[u]=ecnt++;
}
void init(){
    Memset(he, -1);
    Memset(dis, INF);
    Memset(vis, 0);
    Memset(son, 1);
    ecnt=0;
    weight=0;
    scanf("%d%d",&n,&m);
}

struct point
{
    int u;
    mytype l;
    point(int u,mytype l):u(u),l(l) {}
    bool operator<(const point &p) const
    {
        return l>p.l;
    }
};
void prim_heap(int s=1)
{
    priority_queue<point> q;
    q.push(point(s,0));
    weight=0;
    dis[1]=0;
    while(!q.empty())
    {
        point p=q.top();
        q.pop();
        int u=p.u;
        if (vis[u])
            continue;
        vis[u]=1;
        weight+=p.l;//==dis[x]
        for (int i=he[u]; i!=-1; i=e[i].next)
            if (!vis[e[i].v]&&e[i].length<dis[e[i].v])
            {
                dis[e[i].v]=e[i].length;
                pre[e[i].v]=u;
                q.push(point(e[i].v,dis[e[i].v]));
            }
    }

}
void prep(){
    Memset(he, -1);
    ecnt=0;
    for (int i=2; i<=n; i++) {
        adde(pre[i], i, dis[i]);
    }
}
void dfs(int x){
    son[x]=1;
    for (int i = he[x]; i!=-1; i=e[i].next) {
        int v = e[i].v;
        dfs(v);
        son[x]+=son[v];
    }
    return;
}
int main(){
    int t,x,y,l;
    scanf("%d",&t);
    while (t--) {
        init();
        for (int i=1; i<=m; i++) {
            scanf("%d%d%d",&x,&y,&l);
            adde(x, y, l);
            adde(y, x, l);
        }
        prim_heap();
        prep();
        dfs(1);
        ll tmp = 0;
        for (int i=0; i<ecnt; i++) {
            int v = e[i].v;
            ll len = e[i].length;
            tmp+=len*son[v]*(n-son[v]);
        }
        double ans=1.0*tmp*2/(1.0*n*(n-1));
        printf("%lld %.2f\n",weight,ans);
    }
    return 0;
}

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100010
struct node {
    int u, v, w;
    node() {}
    node(int _u, int _v, int _w):u(_u), v(_v), w(_w) {}
};
struct Node{
   int v,len;
   Node(){}
   Node(int _v, int _len):v(_v), len(_len){}
};
vector<Node>vet[N];
vector<node> edge;
int n, m, f[N];
double dp[N];
int sum[N];
bool cmp(const node &x, const node &y) {
    return x.w < y.w;
}
int find_set(int x) {
    if (f[x] == x) return x;
    return f[x] = find_set(f[x]);
}
long long Kruskal() {
    sort(edge.begin(), edge.end(), cmp);
    for (int i = 1; i <= n; i++) f[i] = i;
    long long ans = 0;
    for (int i = 0, u, v, w; i < (int)edge.size(); i++)
    {
        u = edge[i].u, v = edge[i].v, w = edge[i].w;
        u = find_set(u), v = find_set(v);
        if (u == v) continue;
        f[u] = v;
        ans += (long long)w;
        vet[edge[i].u].push_back(Node(edge[i].v,w));
        vet[edge[i].v].push_back(Node(edge[i].u,w));
    }
    return ans;
}
void dfs(int root,int father)
{
   sum[root] = 1;
   for(int i = 0;i < (int)vet[root].size();i++)
    {
      int son = vet[root][i].v;
      int len = vet[root][i].len;
      if(son == father)continue;
      dfs(son,root);
      sum[root] += sum[son];
      dp[root] += dp[son] + ((double)sum[son] * (n - sum[son])) * len;
   }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        edge.clear();
        for (int i = 0, a, b, c; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            edge.push_back(node(a, b, c));
        }
        for(int i = 1;i <= n;i++)vet[i].clear();
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        long long ans = Kruskal();
        dfs(1,0);
        long long s = (long long)n * (n - 1) / 2;
        printf("%I64d %.2f\n",ans,dp[1] / (double)s);
    }
    return 0;
}