HDU 5723 Abandoned country (最小生成树+dfs)-白红宇

HDU 5723 Abandoned country (最小生成树+dfs)

阅读量：4317 次

发布时间：2019-06-06

本文共 2372 字，大约阅读时间需要 7 分钟。

题目链接：

n个村庄m条双向路，从中要选一些路重建使得村庄直接或间接相连且花费最少，这个问题就是很明显的求最小生成树，由于边权各不相同，所以最小生成树唯一。

然后，在这个最小生成树的基础上，求各个路径的最小期望和（推导出期望 = 所有村庄中任意两个村庄距离之和 / 村庄对数）。

最小生成树很好求(边权从小到大，并查集一下就好了)。

然后求以上基础村庄中任意两个村庄距离之和，只要求每条边乘上每条边出现的次数，每条边出现的次数通过观察看出是u相连点个数乘上v相连点个数。这个dfs一遍就可以求。

最后除以村庄对数就好了。

1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               13 using namespace std;14 typedef long long LL;15 typedef pair 
                
                  P;16 const int N = 1e5 + 5;17 int par[N] , num[N]; //num[i]表示以i为根的子树的点个数18 vector 
                  G[N]; //树的各条边19 vector 
                  edge[N*10]; //边权为下标20 21 void init(int n) {22 for(int i = 1 ; i <= n ; ++i) {23 par[i] = i;24 num[i] = 0;25 G[i].clear();26 }27 for(int i = 1 ; i <= 1000000 ; ++i)28 edge[i].clear();29 }30 31 int Find(int n) {32 if(n == par[n])33 return n;34 return par[n] = Find(par[n]);35 }36 37 int dfs(int u , int pre) { //生成树dfs38 num[u] = 1;39 for(int i = 0 ; i < G[u].size() ; ++i) {40 P temp = G[u][i];41 if(temp.first == pre)42 continue;43 num[u] += dfs(temp.first , u);44 }45 return num[u];46 }47 48 LL dfs2(int u , int pre) {49 LL res = 0;50 for(int i = 0 ; i < G[u].size() ; ++i) {51 P temp = G[u][i];52 if(temp.first == pre)53 continue;54 res += dfs2(temp.first , u);55 res += (LL)temp.second * (LL)(num[1] - num[temp.first]) * (LL)num[temp.first];56 }57 return res;58 }59 60 int main()61 {62 int t , n , m , u , v , w;63 scanf("%d" , &t);64 while(t--) {65 scanf("%d %d" , &n , &m);66 init(n);67 for(int i = 0 ; i < m ; ++i) {68 scanf("%d %d %d" , &u , &v , &w);69 edge[w].push_back(P(u , v));70 }71 LL sum = 0; //最小生成树权值72 int cnt = n; //集合数73 for(int i = 1 ; i <= 1000000 ; ++i) {74 if(cnt == 1)75 break;76 if(!edge[i].size()) //因为每条边权值不同 所以每条边对应只有一对点77 continue;78 int faru = Find(edge[i][0].first) , farv = Find(edge[i][0].second);79 if(farv == faru)80 continue;81 par[faru] = farv;82 sum += (LL)i;83 G[edge[i][0].first].push_back(P(edge[i][0].second , i));84 G[edge[i][0].second].push_back(P(edge[i][0].first , i));85 }86 dfs(1 , -1);87 LL res = dfs2(1 , -1); //村庄距离之和88 LL cont = (LL)n * (LL)(n - 1) / 2; //村庄对数89 printf("%lld %.2f\n" , sum , res * 1.0 / cont);90 }91 return 0;92 }

转载于:https://www.cnblogs.com/Recoder/p/5695022.html

你可能感兴趣的文章