hdu 5723 Abandoned country（2016多校第一场）（最小生成树+期望）

Abandoned country

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1756 Accepted Submission(s): 475

Problem Description

An abandoned country has

Input

The first line contains an integer

Output

output the minimum cost and minimum Expectations with two decimal places. They separated by a space.

Sample Input

4 6

1 2 1

2 3 2

3 4 3

4 1 4

1 3 5

2 4 6

Sample Output

6 3.33

Author

HIT

Source

2016 Multi-University Training Contest 1

Recommend

wange2014 | We have carefully selected several similar problems for you: 5733 5732 5731 5730 5729

这题我完全没有思路，比赛时也不会写，看了别人的代码，貌似懂了一点点。。

题意：给了一个图，求最小生成树和期望值，最小生成树指所有的点连接成一条完整的路的最小权值和，期望指图中任意两个点的距离之和除以所有的边的个数（如测试数据：4个点，就是用1-2,1-3,1-4,2-3,2-4,3-4这六条距离的和除以边长总数6）。

附上代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define M 200010
  6 #define ll long long
  7 using namespace std;
  8 ll n,m;
  9 
 10 struct edge
 11 {
 12     int u,v;
 13     int w;
 14 } e[M*5];
 15 
 16 struct node
 17 {
 18     int u,v,w;
 19     int ans;   ///ans记录经过这条边能达到的边的个数
 20     int next;  ///next记录上一次连接的边的序号
 21 }ee[M];
 22 
 23 int father[M],head[M];  ///father数组表示根节点，head记录每条边最后一次连接的边的序号
 24 ll ans,sum;
 25 int tol;
 26 
 27 ll dfs(int u,int p)  ///搜索
 28 {
 29     ll num=0;
 30     for(int i=head[u];i!=-1;i=ee[i].next)
 31     {
 32         if(ee[i].v!=p)
 33         {
 34             ee[i].ans+=dfs(ee[i].v,ee[i].u);
 35             sum+=ee[i].ans*(n-ee[i].ans)*ee[i].w;  ///此边能到达的边的个数*能到此边的边的个数*边的长度
 36           //  cout<<ee[i].ans<<" "<<n-ee[i].ans<<" "<<ee[i].w<<endl;
 37             //cout<<sum<<endl;
 38             num+=ee[i].ans;
 39         }
 40     }
 41     return num;
 42 }
 43 
 44 void add_node(edge a)   ///建立邻接表
 45 {
 46     ee[tol].u=a.u;    ///正向
 47     ee[tol].v=a.v;
 48     ee[tol].w=a.w;
 49     ee[tol].ans=1;
 50     ee[tol].next=head[a.u];
 51     head[a.u]=tol++;
 52     ee[tol].u=a.v;    ///反向
 53     ee[tol].v=a.u;
 54     ee[tol].w=a.w;
 55     ee[tol].ans=1;
 56     ee[tol].next=head[a.v];
 57     head[a.v]=tol++;
 58 }
 59 
 60 int find(int x)   ///搜索根节点
 61 {
 62     while(x!=father[x])
 63         x=father[x];
 64     return x;
 65 }
 66 
 67 void sourch(int x,int y,int z,edge ss)
 68 {
 69     x=find(x);
 70     y=find(y);
 71     if(x!=y)   ///若根节点不相同
 72     {
 73         add_node(ss); ///并且此边存在，建立邻接表
 74         father[x]=y;  ///将其连接在一起
 75         ans+=z;
 76     }
 77 
 78 }
 79 
 80 void init()
 81 {
 82     ans=0,sum=0;
 83     int i,j;
 84     for(i=1; i<=n; i++)
 85     {
 86         father[i]=i;    ///将所有父节点初始定义为自己本身
 87         head[i]=-1;
 88     }
 89     tol=0;
 90     for(i=0; i<m; i++)
 91     {
 92         sourch(e[i].u,e[i].v,e[i].w,e[i]);  ///求最小生成树
 93     }
 94     dfs(1,-1);
 95     ll nn=n*(n-1)/2;
 96     printf("%I64d %.2lf
",ans,(double)sum/nn);
 97 }
 98 
 99 bool cmp(edge a,edge b)
100 {
101     return a.w<b.w;
102 }
103 
104 int main()
105 {
106     int T,i;
107     scanf("%d",&T);
108     while(T--)
109     {
110         scanf("%lld%lld",&n,&m);
111         for(i=0; i<m; i++)
112         {
113             scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); ///记录每边的数据
114         }
115         sort(e,e+m,cmp);  ///要选取最小的花费，因此要进行排序
116         init();
117     }
118     return 0;
119 }

hdu 5723 Abandoned country（2016多校第一场） （最小生成树+期望）

Abandoned country

hdu 5723 Abandoned country（2016多校第一场）（最小生成树+期望）