hdu 4126(prim+树形dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4126

思路：我们可以先求最小生成树，对于最小生成树的每一条边，我们要找到它的最佳替代边，使其价值最小。

具体实践方法：

假设两个各自连通的部分分别为树A，树B,dp[i][j]表示树A中的点i到树B(点j所在的树的最近距离）,这个很容易用dfs实现,然后通过求出的dp[i][j]，再用一个dfs求出树B到树A的最近距离（就是枚举树A中的所有点到树B的最近距离，取其中的最小值），这个求出来的值其实就是我们要求的最佳替代边，将它保存到一个数组中即可。总的时间复杂度为O(n^2)。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace  std;
  7 #define MAXN 3030
  8 #define inf  1000000000
  9 typedef __int64 LL;
 10 vector<int>edge[MAXN];
 11 int map[MAXN][MAXN];
 12 int lowcost[MAXN];
 13 int nearvex[MAXN];
 14 int n,m,q;
 15 LL sumweight;
 16 int dp[MAXN][MAXN];//树A中的i点到树B中的点j的最近距离
 17 int mindist[MAXN][MAXN];//保存最佳替换边
 18 bool mark[MAXN];
 19 
 20 void Prim(int u0)
 21 {
 22     memset(mark,false,(n+2)*sizeof(int));
 23     for(int i=1;i<n;i++){
 24         lowcost[i]=map[u0][i];
 25         nearvex[i]=u0;
 26     }
 27     mark[u0]=true;
 28     lowcost[u0]=inf;
 29     nearvex[u0]=-1;
 30     sumweight=0;
 31     for(int i=0;i<n-1;i++)
 32     {
 33         int min=inf,v=-1;
 34         for(int j=1;j<n;j++){
 35             if(!mark[j]&&lowcost[j]<min){
 36                 v=j,min=lowcost[j];
 37             }
 38         }
 39         sumweight+=lowcost[v];
 40         mark[v]=true;
 41         if(v!=-1)
 42         {
 43             edge[v].push_back(nearvex[v]);
 44             edge[nearvex[v]].push_back(v);
 45             for(int j=1;j<n;j++)
 46             {
 47                 if(!mark[j]&&map[v][j]<lowcost[j]){
 48                     lowcost[j]=map[v][j];
 49                     nearvex[j]=v;
 50                 }
 51             }
 52         }
 53     }
 54 }
 55 
 56 int dfs1(int u,int father,int rt)
 57 {
 58     for(int i=0;i<edge[u].size();i++){
 59         int v=edge[u][i];
 60         if(v==father)continue;
 61         dp[rt][u]=min(dp[rt][u],dfs1(v,u,rt));
 62     }
 63     if(father!=rt)dp[rt][u]=min(dp[rt][u],map[rt][u]);
 64     return dp[rt][u];
 65 }
 66 
 67 int dfs2(int u,int father,int rt)
 68 {
 69     int ans=dp[u][rt];
 70     for(int i=0;i<edge[u].size();i++){
 71         int v=edge[u][i];
 72         if(v==father)continue;
 73         ans=min(ans,dfs2(v,u,rt));
 74     }
 75     return ans;
 76 }
 77 
 78 void Solve()
 79 {
 80     int u,v,w;
 81     scanf("%d",&q);
 82     double ans=0;
 83    // for(int i=0;i<n;i++)printf("%d***\n",nearvex[i]);
 84     for(int i=1;i<=q;i++)
 85     {
 86         scanf("%d%d%d",&u,&v,&w);
 87         if(nearvex[u]!=v&&nearvex[v]!=u){
 88             ans+=sumweight*1.0;
 89         }else {
 90             ans+=sumweight*1.0-map[u][v]+min(mindist[u][v],w);
 91         }
 92     }
 93     printf("%.4lf\n",ans/q);
 94 }
 95 
 96 
 97 int main()
 98 {
 99     int u,v,w;
100     while(scanf("%d%d",&n,&m),(n+m))
101     {
102         for(int i=0;i<n;i++)edge[i].clear();
103         for(int i=0;i<n;i++)
104             for(int j=0;j<n;j++)
105                 map[i][j]=dp[i][j]=inf;
106         for(int i=0;i<m;i++){
107             scanf("%d%d%d",&u,&v,&w);
108             map[u][v]=map[v][u]=w;
109         }
110         Prim(0);
111         for(int i=0;i<n;i++)
112             dfs1(i,-1,i);
113         for(int i=0;i<n;i++){
114             for(int j=0;j<edge[i].size();j++)
115             {
116                 int v=edge[i][j];
117                 mindist[i][v]=mindist[v][i]=dfs2(v,i,i);
118             }
119         }
120         Solve();
121     }
122     return 0;
123 }

View Code

ps：hdoj上G++能过，但不知C++为何就过不了呢。