题意简单：去掉最小生成树的某一条边并补上一条，求MaxVal

思路：贪心（借鉴Yamidie的思路。。。）

分别求出最小生成树和次最小生成树，再在这两棵树上求最小生成树

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 1015;const int maxm = maxn*maxn;const int inf1 = 0x3f3f3f3f;const double inf2 = 9999999999;struct Point {    double x,y;}pnt[ maxn ];struct Edge{    int u,v;    double val;    int id;}edge[ maxn<<1 ];int cnt_edge;double mat[ maxn ][ maxn ];double dis[ maxn ];bool vis[ maxn ];int pre[ maxn ];double LenPrim1;double LenPrim2;int fa[ maxn ],rank[ maxn ];int find( int x ){    if( x==fa[x] ) return x;    else return fa[ x ] = find( fa[x] );}void init( int n ){    for( int i=0;i
         
          dis[j] ){ M = dis[j]; id = j; } } if( id==-1 ) break; vis[ id ] = true; ans += M; edge[ cnt_edge ].u = pre[ id ]; edge[ cnt_edge ].v = id; edge[ cnt_edge ].id = Belong; edge[ cnt_edge ].val = mat[ id ][ pre[id] ]; //printf("u = %d,v = %d\n",edge[cnt_edge].u,edge[cnt_edge].v); cnt_edge ++ ; for( int j=0;j
          
           mat[id][j] ){ dis[j] = mat[id][j]; pre[ j ] = id; } } } return ans;} void Deal( int n ){ for( int i=0;i
           
            ans ) ans = temp_ans; } } printf("%.2lf\n",ans*k); } return 0;}