P1340 兽径管理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.离线化。

题意：

有n个点，m条边，每次加入一条边，求加边后形成的最小生成树的大小。

分析：

先把加边顺序储存起来，倒序删边，如果生成树中有边被删去，重建生成树。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=210;
int n,m,fa[N],vis[6010],ans[6010],dlt[6010];
struct node{
    int from,to,id,len;
    bool operator <(const node &b)const{
        return len<b.len;
    }
}line[6010];

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void kruskal(int x){
    //cout<<"   case 1 "<<x<<endl;//
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)fa[i]=i;
    int js=0;
    for(int i=1;i<=m;i++){
        if(dlt[line[i].id])continue;
        int u=find(line[i].from),v=find(line[i].to);
        if(u!=v){
            ++js;
            vis[line[i].id]=1;
            ans[x]+=line[i].len;
            fa[u]=v;
        }
        if(js==n-1)break;
    }
    if(js!=n-1)ans[x]=-1;
}

int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        line[i].from=read();line[i].to=read();line[i].len=read();
        line[i].id=i;
    }
    sort(line+1,line+m+1);
    kruskal(m);
    for(int i=m-1;i>=1;i--){
        dlt[i+1]=1;
        if(vis[i+1])kruskal(i);
        else ans[i]=ans[i+1];
        if(ans[i]==-1){
            for(int j=1;j<i;j++)ans[j]=-1;
            break;
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    return 0;
}