P1340 兽径管理

传送门

思路：

　　题目要求每次连边都要输出最小生成树的边权和。如果在线直接套用最小生成树模板肯定会超时，考虑离线处理。记录每一插入边的时间，在所有边都插入完成后排序一遍就可以求最小生成树（按照插入时间的前后对边进行取舍）。

标程：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<string>

#include<vector>

#include<stack>

#include<deque>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define maxn 6001

typedef long long LL;

LL n,w,cnt,ans;

LL fa[maxn];

struct hh

{

    LL l,r,w,tim;

}t[maxn];

inline LL read()

{

    LL xs=,kr=;char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline bool cmp(const hh&l,const hh&r)

{

    return l.w<r.w;

}

inline LL find(LL u)

{

    if(u!=fa[u]) fa[u]=find(fa[u]);

    return fa[u];

}

inline void kruskal(LL num)

{

    for(LL i=;i<=w;i++) fa[i]=i;

    for(LL i=;i<=w;i++)

    {

        if(t[i].tim>num) continue;

        LL r1=find(t[i].l),r2=find(t[i].r);

        if(r1!=r2)

        {

            fa[r1]=r2;

            ans+=t[i].w;

            cnt++;

        }

        if(cnt==n-) {printf("%lld\n",ans);return;}

    }

    printf("-1\n");

}

int main()

{

    n=read();w=read();

    for(LL i=;i<=w;i++)

    {

        t[i].l=read();t[i].r=read();t[i].w=read();t[i].tim=i;

    }

    sort(t+,t+w+,cmp);

    for(LL i=;i<=w;i++)

    {

        ans=,cnt=;

        kruskal(i);

    }

return ;

}