【図論】【最小生成ツリー】[IOI 2003]maintain

タイトル説明:ここをクリックして構想を解きます:辺をプラスする同時に辺に対して順序を挿入して、辺の数量≧n-1の時、kruskalを行って、この時毎回kruscalの複雑度はO(m)、アルゴリズムの時間の複雑度はO(m^2)です
インプリメンテーションコード

#include<cstdio>
#include<cstring>
#define INF 0x7f7f7f7f
#define MAXN 200
#define MAXM 6000
#include<algorithm>
using namespace std;
int n,w,fa[MAXN+10],ans;
struct node{
    int u,v,wt;
}edge[MAXM+10];
int find_fa(int x){
    if(fa[x]==x)
        return x;
    return find_fa(fa[x]);
}
int kruskal(int ne){
    int i,j=0,u,v,ret=0;
    for(i=1;i<=n;i++)
        fa[i]=i;
    for(i=1;i<n;i++){
        for(j++;j<=ne;j++){
            u=edge[j].u,v=edge[j].v;
            fa[u]=find_fa(u);
            fa[v]=find_fa(v);
            if(fa[u]!=fa[v]){
                ret+=edge[j].wt;
                fa[fa[v]]=fa[u];
                break;
            }
        }
        if(j>ne)
            return -1;
    }
    return ret;
}
int main()
{
    int i,j,k;
    scanf("%d%d",&n,&w);
    for(i=1;i<=w;i++){
        node t;
        scanf("%d%d%d",&t.u,&t.v,&t.wt);
        for(j=1;j<i;j++)
            if(edge[j].wt>t.wt){
                for(k=i;k>j;k--)
                    edge[k]=edge[k-1];
                break;
            }
    edge[j]=t;
        if(i<n-1){
            puts("-1");
            continue;
        }
        printf("%d
",kruskal(i));
    }
}