题目链接：

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

具体实践方法：

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

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace  std;  7 #define MAXN 3030  8 #define inf  1000000000  9 typedef __int64 LL; 10 vector
           
            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
           
          
         
        
       
      

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