题目描述

农夫约翰要把他的牛奶运输到各个销售点。

运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。

运输的总距离越小，运输的成本也就越低。

低成本的运输是农夫约翰所希望的。

不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。

现在请你帮忙找到该运输方案。

注意：：

如果两个方案至少有一条边不同，则我们认为是不同方案；
费用第二小的方案在数值上一定要严格小于费用最小的方案；
答案保证一定有解；
输入格式
第一行是两个整数 N,M，表示销售点数和交通线路数；

接下来 M 行每行 3 个整数 x,y,z，表示销售点 x 和销售点 y 之间存在线路，长度为 z。

输出格式
输出费用第二小的运输方案的运输总距离。

数据范围
1≤N≤500,
1≤M≤104,
1≤z≤109,
数据中可能包含重边。

样例

输入样例：
4 4
1 2 100
2 4 200
2 3 250
3 4 100
输出样例：
450

次小生成树

求出最小生成树后，需要用非树边去替换树边
而对于非树边来说（a,b为非树边的两个端点），如果要用当前边替换进入
可以断了a~b中的其中一条边，然后最小生成树因此变成了两棵树（a->… , …->b->…）
再加上当前的非树边，将两棵树连接在一起
连接后的树的权值一定要最越大越好，生成树的权值=最小生成树权值-删去的树边+添加的非树边
其中删去的树边权值是越大越好，因此呢，是需要求出a到b中最大的权值边，
但是可能存在最大的权值边等于添加的非树边，因此可以用次小边代替

思路

1，求出最小生成树，并且存储所有的数边
2，在深搜枚举每个点到达其他点的第一小边，和第二小边。需要注意的是，第二小边是需要严格大于第一小边的，否则对于最小树边和当前枚举的非树边长度相同时，就不能替换了，但此时却可以替换长度次大的树边。所以第二小边需要严格小于第一小边
3，枚举每一条非树边，找出替换后的树的最小权值

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=510,M=1e4+10;
typedef long LL;

struct NODE{
    int a,b,w;
    bool flag;
    bool operator <(const NODE &c)const{
        return w<c.w;
    }
}node[M];
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int dist1[N][N];
int dist2[N][N];
int n,m;
int f[N];

void add(int a,int b,int c){
    ne[idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx++;
}

int find(int x){
    if(x!=f[x]) f[x]=find(f[x]);
    return f[x];
}

void dfs(int u,int fa,int max1,int max2,int d1[],int d2[]){
    d1[u]=max1;
    d2[u]=max2;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=fa){
            int t1=max1,t2=max2;
            if(w[i]>t1) t2=t1,t1=w[i];
            else if(w[i]<t1&&w[i]>t2) t2=w[i];
            dfs(j,u,t1,t2,d1,d2);
        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;

    for(int i=0;i<m;i++){
        cin>>node[i].a>>node[i].b>>node[i].w;
    }
    sort(node,node+m);
    LL sum=0;
    for(int i=0;i<m;i++){
        int a=node[i].a, b=node[i].b, w=node[i].w;
        int fa=find(a), fb=find(b);
        if(fa!=fb){
            f[fa]=fb;
            sum+=w;
            node[i].flag=true;
            add(a,b,w),add(b,a,w);
        }
    }

    for(int i=1;i<=n;i++) dfs(i,-1,0,0,dist1[i],dist2[i]);

    LL res=1e18;
    for(int i=0;i<m;i++){
        if(!node[i].flag){
            int a=node[i].a, b=node[i].b, w=node[i].w;
            if(w>dist1[a][b]){
                res=min(res,sum+w-dist1[a][b]);
            }
            else if(dist2[a][b]<w){
                res=min(res,sum+w-dist2[a][b]);
            }
        }
    }
    cout<<res<<endl;
    return 0;
}