[JZOJ3806] 小X的道路修建

Description

因为一场不小的地震，Y 省n 个城市之间的道路都损坏掉了，省长希望小X 将城市之间的道路重修一遍。
很多城市之间的地基都被地震破坏导致不能修路了，因此可供修建的道路只有m 条。因为施工队伍有限，省长要求用尽量少的道路将所有的城市连通起来，这样施工量就可以尽量少。不过，省长为了表示自己的公正无私，要求在满足上述条件的情况下，选择一种方案，使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小，即使这样的方案会使总价提升很多也没关系。
小X 现在手忙脚乱，希望你帮帮他。
2 ≤ n ≤ 2000，0 ≤ m ≤ 15000，a!=b，1 ≤ c ≤ 2 × 10^9。

Code

联通且边数最小，那只能是一棵树了。

先把所有的边按边权从大到小排个序。

那就维护生成树，一条一条加边。

如果加了这个边能构成环那就将这个环上的边权最大的边弄出来，删掉，加上这条边，显然答案是最优的，可以DFS直接跑。

如果不能构成环就直接加。
当边数等于n−1时更新答案即可。

Ofcourse，因为这是一棵树，支持删边加边，我这蒟蒻就只能眼睁睁看着某些神犇直接Copy了LCT的板子。。。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 2005
#define M 30005
#define INF 2147483647
using namespace std;
int lt[M],nt[M],fs[N],dt[M],pr[M],fr[M],n,m,mx,mz,mis,n1,fx[M];
struct node
{
    int x,y,z;
}rd[M];
bool cmp(node x,node y)
{
    return x.z>y.z;
}
void link(int x,int y,int z)
{
    nt[++n1]=fs[x];
    lt[fs[x]]=n1;
    dt[n1]=y;
    pr[n1]=z;
    fr[n1]=x;
    fs[x]=n1;
}
void delt(int k)
{
    if(fs[fr[k]]==k) fs[fr[k]]=nt[k];
    nt[lt[k]]=nt[k];
    lt[nt[k]]=lt[k];
}
bool find(int k,int t,int f)
{   
    if(t==k) return 1;
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(p==f) continue;
        if(find(p,t,k))
        {
            if(pr[i]>mz)
            {
                mx=i;
                mz=pr[i];
            }
            return 1;
        }
    }
    return 0;
}
int get(int k,int f)
{
    int s=0;
    for(int i=fs[k];i;i=nt[i])
    {
        int p=dt[i];
        if(p==f) continue;
        s=max(s,max(pr[i],get(p,k)));
    }
    return s;
}
int main()
{
    cin>>n>>m;
    int m1=0;
    n1=0;
    fo(i,1,m)
    {
        mz=0;
        scanf("%d%d%d",&rd[i].x,&rd[i].y,&rd[i].z);
    }
    sort(rd+1,rd+m+1,cmp);
    int ans=INF;
    fo(i,1,m)
    {
        mz=0;
        mis=rd[i].z;
        if(find(rd[i].x,rd[i].y,0))
        {
            link(rd[i].x,rd[i].y,rd[i].z);
            link(rd[i].y,rd[i].x,rd[i].z);
            fx[n1-1]=n1;
            fx[n1]=n1-1;
            delt(mx);
            delt(fx[mx]);
        }
        else
        {
            link(rd[i].x,rd[i].y,rd[i].z);
            link(rd[i].y,rd[i].x,rd[i].z);
            fx[n1-1]=n1;
            fx[n1]=n1-1;
            m1++;
        }
        if(m1==n-1) ans=min(ans,get(1,0)-mis);
    }
    if(ans==INF) cout<<-1;
    else cout<<ans;
}