题目大意：

求原图的最小生成树，和次小生成树。

题目分析：

kruskals求mst（\(O(mlogm)\)）

考虑次小生成树暴力的做法，因为次小生成树总是由最小生成树删掉一条边并添加一条边得到的，所以可以枚举最小生成树上的每一条边删去，再重新求一遍mst。(\(O(m^2logm)\))

下面的题解来自：(\(O(n^2(求最大权值) + mlogm(求最小生成树) + m(求次小))\))

code

#include
    
     using namespace std;const int N = 550, M = 150050, OO = 0x3f3f3f3f;int n, ans, m;struct node{    int x, y, dis;    inline bool operator < (const node &b) const{        return dis < b.dis;    }}edge[M];int d[N][N];bool vst[N], used[M];namespace mst{    int ecnt, adj[N], nxt[M << 1], go[M << 1], len[M << 1];    inline void addEdge(int u, int v, int c){        nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = c;        nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u, len[ecnt] = c;    }    int anc[N];    inline int getAnc(int x){        return x == anc[x] ? x : (anc[x] = getAnc(anc[x]));    }    inline int kruskals(){        int ret = 0;        sort(edge + 1, edge + m + 1);        for(int i = 1; i <= m; i++){            int fx =  getAnc(edge[i].x), fy = getAnc(edge[i].y);            if(fx != fy) anc[fx] = fy, ret += edge[i].dis, addEdge(edge[i].x, edge[i].y, edge[i].dis), used[i] = true;        }        return ret;    }    inline void dfs(int now, int u, int f, int mx){        d[now][u] = d[u][now] = mx;        for(int e = adj[u]; e; e = nxt[e]){            int v = go[e];            if(v == f) continue;            dfs(now, v, u, max(mx, len[e]));        }    }} int main(){    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++) mst::anc[i] = i;    for(int i = 1; i <= m; i++){        int x, y, c; scanf("%d%d%d", &x, &y, &c);        edge[i] = (node){x, y, c};    }    ans = mst::kruskals();    if(n - 1 == mst::ecnt / 2) printf("Cost: %d\n", ans);    else printf("Cost: -1\nCost: -1\n");    int ans1 = OO;    for(int i = 1; i <= n; i++)        mst::dfs(i, i, 0, 0);    for(int i = 1; i <= m; i++){        if(used[i]) continue;        int x = edge[i].x, y = edge[i].y;        ans1 = min(ans1, ans - d[x][y] + edge[i].dis);    }    if(ans1 != OO) printf("Cost: %d", ans1);    else printf("Cost: -1");    return 0;}