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

时间:2022-12-18 20:20:49

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5723

【题目大意】

  n座城市,m条路径,求解:

    1.最短的路径和,使得n座城市之间直接或者间接连通

    2.在路径和最短的情况下,求出任意两个城市之间的期望距离

【题解】

  对于问题1,只需求出该图的最小生成树,边权和即答案,由于边权值唯一,因此不存在最小生成树多解的情况。

  对于问题2,期望的通常求法为(任意两点之间的路径和)/(点对数)

  那么问题就转化为任意两点间距离和的问题,我们按边考虑,对于每条树上的边,它对答案的贡献值为左边的点数×右边的点数×边权,搜索每个记录每棵子树的大小,对于子树和父节点相连的这条边,他左右两边的点数分别为(总点数-子树大小)和(子树大小),那么递归计算答案即可。

【代码】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000005;
int T,n,m,f[N],nxt[N],w[N],v[N],cnt[N],g[N],ed;
double ans1,ans2;
struct data{int x,y,z;}a[N];
bool cmp(data a,data b){return a.z<b.z;}
int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}
void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int pre){
cnt[x]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre){
dfs(v[i],x);
cnt[x]+=cnt[v[i]];
ans2+=2.0*cnt[v[i]]*(n-cnt[v[i]])*w[i];
}
}
int main(){
scanf("%d",&T);
while(T--){
ans1=ans2=ed=0;
memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt));
memset(w,0,sizeof(w)); memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
if(sf(a[i].x)==sf(a[i].y))continue;
f[sf(a[i].x)]=sf(a[i].y);
ans1+=a[i].z;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
}dfs(1,1);
printf("%.0f %.2f\n",ans1,ans2/n/(n-1));
}return 0;
}

HDU 5723 Abandoned country(最小生成树 + 树形DP)的更多相关文章

  1. HDU 5723 Abandoned country 最小生成树&plus;搜索

    Abandoned country Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others ...

  2. hdu 5723 Abandoned country 最小生成树 期望

    Abandoned country 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5723 Description An abandoned coun ...

  3. hdu 5723 Abandoned country 最小生成树&plus;子节点统计

    Abandoned country Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others ...

  4. HDU 5723 Abandoned country &lpar;最小生成树&plus;dfs&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5723 n个村庄m条双向路,从中要选一些路重建使得村庄直接或间接相连且花费最少,这个问题就是很明显的求最 ...

  5. Abandoned country&lpar;最小生成树&plus;树形DP&rpar;

    #include<bits/stdc++.h> using namespace std; struct node{ int u, v, w, nex; bool gone; node(){ ...

  6. 最小生成树 kruskal hdu 5723 Abandoned country

    题目链接:hdu 5723 Abandoned country 题目大意:N个点,M条边:先构成一棵最小生成树,然后这个最小生成树上求任意两点之间的路径长度和,并求期望 /************** ...

  7. HDU 5723 Abandoned country(落后渣国)

    HDU 5723 Abandoned country(落后渣国) Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 ...

  8. HDU 5723 Abandoned country 【最小生成树&amp&semi;&amp&semi;树上两点期望】

    任意门:http://acm.hdu.edu.cn/showproblem.php?pid=5723 Abandoned country Time Limit: 8000/4000 MS (Java/ ...

  9. HDU 5723 Abandoned country (最小生成树 &plus; dfs)

    Abandoned country 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5723 Description An abandoned coun ...

  10. HDU 5723 Abandoned country&lpar;kruskal&plus;dp树上任意两点距离和&rpar;

    Problem DescriptionAn abandoned country has n(n≤100000) villages which are numbered from 1 to n. Sin ...

随机推荐

  1. 遗传算法的C语言实现&lpar;一&rpar;&colon;以非线性函数求极值为例

    以前搞数学建模的时候,研究过(其实也不算是研究,只是大概了解)一些人工智能算法,比如前面已经说过的粒子群算法(PSO),还有著名的遗传算法(GA),模拟退火算法(SA),蚁群算法(ACA)等.当时懂得 ...

  2. Android Studio使用百度地图示例BaiduMapsApiASDemo

    Android Studio使用百度地图示例BaiduMapsApiASDemo 用自己AVD下的debug.keystore替换掉项目中的debug.keystore 生成自己的签名 同样的方法生成 ...

  3. 为什么一个object&lowbar;id在dba&lowbar;objects中为什么查不到记录?

    SQL> drop table test purge;SQL> create table test (id int,comments CLOB); SQL> select INDEX ...

  4. android NDK 实用学习(五)-c&plus;&plus;端调用java接口

    1,阅读此文章前请阅读前面文章,以免阅读出现障碍: android NDK 实用学习(一)-获取java端类及其类变量 android NDK 实用学习(二)-java端对象成员赋值和获取对象成员值 ...

  5. Markdown&plus;Pandoc 最佳写作拍档 &lpar;mailp&period;in&rpar;

    Markdown+Pandoc 最佳写作拍档 我们为什么写作? 自从人们开始写作,写作便是记录.抒发.批判.反省的好工具.从石板上的刻印到笔墨纸砚,再到如今的信息时代.从静态的个人主页到托管博客,从个 ...

  6. WPF的AutoCompleteBox控件

    AutoCompleteBox怎么用,网上都能查得到,本文就不再赘述. 最近在用的时候,发现一个小BUG,当匹配数据的个数超过了Drop页面能够显式的数据个数时,如果此时一直按键盘上“向下的箭头”,你 ...

  7. Lodop删除语句Deleted只能内嵌设计维护可用

    有些人想用类似如下的语句删除打印项,或判断后把不需要的打印项删除,这种删除语句只能在打印设计或打印维护内嵌的时候使用,打印预览内嵌也不能使用.LODOP.SET_PRINT_STYLEA(2,'Del ...

  8. Office 2010激活 NO KMS products detected问题

    今天用office2010激活工具Office 2010 Toolkit激活安装的office2010时悲剧的遇到了这个问题,如下图: (这张图是从网上找的,不过和我遇到的问题是一样的). 然后上网搜 ...

  9. Python 为什么sys&period;stdout&period;write 输出时后面总跟一个数字

    sys.stdout 是标准输出文件.write就是往这个文件写数据. 合起来就是打印数据到标准输出 因为-在交互模式下会输出函数返回值,而write会返回输出的字符数量.在命令行里不会显示

  10. 基于 Flutter 以两种方式实现App主题切换

    概述 App主题切换已经成为了一种流行的用户体验,丰富了应用整体UI视觉效果.例如,白天夜间模式切换.实现该功能的思想其实不难,就是将涉及主题的资源文件进行全局替换更新.说到这里,我想你肯定能联想到一 ...