題意:
? ? ? 這個題目和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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。