秘密的牛奶运输(次最小生成树)

• 给定 n n n个点和 m m m条边，求 次最小生成树 的代价。
• 如果两个方案至少有一条边不同，则我们认为是不同方案；
• 费用第二小的方案在数值上一定要严格大于费用最小的方案；
• 答案保证一定有解；

1：求最小生成树，统计标记每条边是树边，还是非树边；同时把最小生成树建立出来。
2：预处理任意两点间的边权最大值和次大值(可能出现非树边和边权最大值相等情况)。
3：依此枚举所有非树边，求 m i n ( s u m + w + d i s t [ a ] [ b ] ) min(sum+w+dist[a][b]) min(sum+w+dist[a][b])，满足 w > d i s t [ a ] [ b ] w>dist[a][b] w>dist[a][b]，此处的 s u m sum sum是最小生成树的代价。

• 首先是次最大值的注意，上述提过，如果不存一个两点间路径上边权的次大值，那么遇到数据：

5 5
1 2 1
2 3 2
3 4 2
4 5 1
2 5 2

• 便会遇到问题，前四条边可以构造最小生成树，总代价 s u m sum sum是 6 6 6。而当最后的 d i s t [ 2 ] [ 5 ] dist[2][5] dist[2][5]加入用以构造次最小生成树时会发现边权最大值是 2 2 2无法进行更新，但显然路径中存在一条边权是 1 1 1的边，可以构造成次最小生成树且总贡献是 s u m − 1 + 2 sum-1+2 sum−1+2。因此我们要存下边权次大值(严格小于边权最大值)。
• DFS 里的递归 m a x 1 max1 max1和 m a x 2 max2 max2需要开变量存储，否则直接更新 m a x 1 max1 max1和 m a x 2 max2 max2会对其余边产生影响，即下述参考代码中的 t 1 t1 t1和 t 2 t2 t2。
• 更新最终次最小生成树的值时需要分类进行判断，看看选择 m a x 1 max1 max1还是 m a x 2 max2 max2。
• 本题会爆Int，因此需要开LongLong。

#include
using namespace std;
#define int long long 
#define lowbit(x)(x&-x)
typedef pairPII;
const int INF = 0x3f3f3f3f;
typedef pairPIS;
typedef pairPDD;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
const int N = 510,M = 1e4+10;
int h[N],ne[M<<1],e[M<<1],idx,w[M<<1];
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
struct Node{
    int a,b,w;
    bool flag;//判断是否是树边
    bool operator<(const Node &W)const{
        return w
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
void dfs(int u,int fa,int maxn1,int maxn2,int d1[],int d2[]){//d代表2维内容
    d1[u]=maxn1,d2[u]=maxn2;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        int t1=maxn1,t2=maxn2;
        if(w[i]>t1){
            t2=t1;
            t1=w[i];
        }
        else if(w[i]>t2){
            t2=w[i];
        }
        dfs(j,u,t1,t2,d1,d2);
    }
}
signed main(){
    snow
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        nodes[i]={a,b,w};
    }
    sort(nodes+1,nodes+1+m);
    //kruskal最小生成树
    for(int i=1;i<=n;i++)p[i]=i;
    int all=0;//最小生成树的代价
    for(int i=1;i<=m;i++){
        int a=nodes[i].a;
        int b=nodes[i].b;
        int w=nodes[i].w;
        int pa=find(a),pb=find(b);
        if(pa!=pb){
            p[pa]=pb;
            nodes[i].flag=true;
            add(a,b,w);
            add(b,a,w);
            all+=w;
        }
    }
    for(int i=1;i<=n;i++)dfs(i,-1,0,0,dist1[i],dist2[i]);
    int end=1e18;
    for(int i=1;i<=m;i++){
        if(!nodes[i].flag){
            int a=nodes[i].a;
            int b=nodes[i].b;
            int w=nodes[i].w;
            int t;
            if(dist1[a][b]