P1340 兽径管理

首先依次加边，直到整个图联通为止，之前均输出，

图刚连通时跑一遍正常的克鲁斯卡尔。

然后将用到的边存起来（只有条），

之后每加一条边，就对将这条边排序，

再跑就可以了。

复杂度（快排）

（插入排序）

#include<algorithm>
#include<iostream>
#include<cstdio>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=25000;
struct Bian{
    int a,b,v;
    bool operator <(const Bian &bb)const{
        return v<bb.v;
    }
}bian[100000],dq[100000];

int n,ci,zt,ji,Ans,fa[maxn];
int find(int e){return fa[e]=(fa[e]==e)?(e):(find(fa[e]));}
int main(){
    scanf("%d%d",&n,&ci);
    rep(i,1,n)fa[i]=i;ji=n;
    rep(i,1,ci){
        if(zt==0){
            scanf("%d%d%d",&bian[i].a,&bian[i].b,&bian[i].v);
            int faa=find(bian[i].a),fab=find(bian[i].b);
            if(faa!=fab){
                fa[faa]=fab;
                ji--;
            }
            if(ji==1){
                zt=1;
                rep(j,1,n)fa[j]=j;
                sort(bian+1,bian+i+1);
                Ans=0;int tot=0;
                rep(j,1,i){
                    faa=find(bian[j].a),fab=find(bian[j].b);
                    if(faa!=fab){
                        dq[++tot]=bian[j];
                        fa[faa]=fab;
                        Ans+=bian[j].v;
                    }
                }
                printf("%d\n",Ans);
                continue;
            }
            else{
                printf("-1\n");
                continue;
            }
        }
        else{
            scanf("%d%d%d",&dq[n].a,&dq[n].b,&dq[n].v);
            sort(dq+1,dq+n+1);
            rep(j,1,n)fa[j]=j;
            Ans=0;
            int de;
            rep(j,1,n){
                int faa=find(dq[j].a),fab=find(dq[j].b);
                if(faa!=fab){
                    fa[faa]=fab;
                    Ans+=dq[j].v;
                }
                else de=j;
            }
            rep(j,de,n-1)dq[j]=dq[j+1];
            printf("%d\n",Ans);
        }
    }
    return 0;
}