hdu4126(MST + 树形dp

生活随笔 收集整理的这篇文章主要介绍了 hdu4126(MST + 树形dp 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题意:
      这个题目和hdu4756差不多,是给你一个图,然后是q次改变边的权值,权值只增不减,最后问你每次改变之后的最小树的平均值是多少.

思路:(prim+树形dp)

      先跑一边最小树(建议用普利姆,别用克鲁斯卡尔,虽然网上有用k过的,但我感觉理论上会超时 n*n*nlog(n)/2),然后树形dp跑出任意两个集合之间的最有替代边.(n^2),然后当每次输入一条要该边的边的时候,先判断先是不是最小树上的边,如果不是那么sum直接加最小树,如果是那么就用sum - dis[u][v] + min(dis ,dp[u][v]);就是用原边和不用原边的最小值,记住此时的原边权值已经改变....

#include<stdio.h> #include<string.h> #include<algorithm>#define N (3000 + 100) #define inf 9223372036854775807 using namespace std;typedef struct {int to ,next; }STAR;STAR E[N*2]; int list[N] ,tot; double map[N][N]; double dp[N][N];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].next = list[b];list[b] = tot; }double minn(double a ,double b) {return a < b ? a : b; }double DFS_T_DP(int p ,int s ,int f) {double now = inf;for(int k = list[s] ;k ;k = E[k].next) {int to = E[k].to;if(to == f) continue;double tmp = DFS_T_DP(p ,to ,s);now = minn(tmp ,now);dp[s][to] = dp[to][s] = minn(dp[s][to] ,tmp);} if(f != p)now = minn(now ,map[p][s]);return now; }struct PRIM //从0开始用 { double d[N];int vis[N]; bool mp[N][N]; //标记最小生成树上的边 double ans;//最小树 int n;//点的个数 记得初始化 *** double dis[N][N]; // 距离 记得初始化 ***** void prim() { for(int i=0;i<n;i++){ vis[i]=0; d[i]=dis[0][i]; } vis[0]=-1; ans=0; memset(mp,0,sizeof(mp)); for(int i=1;i<n;i++){ double Min= inf; int node=-1; for(int j=0;j<n;j++){ if(vis[j]!=-1 && d[j]<Min){ node=j; Min=d[j]; } } ans+=Min; mp[vis[node]][node]=mp[node][vis[node]]=1; add(vis[node],node); // 建树 vis[node]=-1; for(int j=0;j<n;j++){ if(vis[j]!=-1 && d[j]>dis[node][j]){ vis[j]=node; d[j]=dis[node][j]; } } } } }P;int main () {int n ,m ,q ,i ,j ,a ,b;double dis;while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 0 ;i <= n ;i ++){for(j = i + 1 ;j <= n ;j ++)P.dis[i][j] = P.dis[j][i] = map[i][j] = map[j][i] = dp[i][j] = dp[j][i] = inf;P.dis[i][i] = P.dis[i][i] = map[i][i] = map[i][i] = 0;}for(i = 1 ;i <= m ;i ++){scanf("%d %d %lf" ,&a ,&b ,&dis);map[a][b] = map[b][a] = dis;P.dis[a][b] = P.dis[b][a] = dis;}P.n = n;memset(list ,0 ,sizeof(list));tot = 1;P.prim();double T_sum = P.ans;for(i = 0 ;i < n ;i ++)DFS_T_DP(i ,i ,-1);double ans_sum = 0; scanf("%d" ,&q); for(i = 1 ;i <= q ;i ++){scanf("%d %d %lf" ,&a ,&b ,&dis);double now;if(!P.mp[a][b])now = T_sum ; else{if(dis > dp[a][b])now = T_sum - map[a][b] + dp[a][b] ; elsenow = T_sum - map[a][b] + dis ; } ans_sum += now;}printf("%.4lf\n" ,ans_sum / q);}return 0; }

总结

以上是生活随笔为你收集整理的hdu4126(MST + 树形dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：hdu4126(MST + 树形dp https://m.mxgxt.com/news/view/1965440

相关内容

dp ... 什么意思 dp是什么 ... 术语
DP
饭圈用语dp是什么意思 常见饭圈缩写dp的含义
饭圈用语dp是什么意思 类似dp的网络术语有哪些
怎么理解饭圈dp，何谓“饭圈”
怎么理解饭圈dp
dp是什么意思网络术语，饭圈（带领粉丝围攻黑粉）
主持人杨阳专访明星网红造型店DP国际创始人陈有军
openoj的一个小比赛（F题解题报告）poj3978(dp+素数筛选）
基于信息化的DP公司采购供应链管理研究

随便看看