题解

此题还是很有难度的。

想到不能对每个点都求一遍最小生成树，于是逆序求解，如果当前到不了，那以后都到不了，直接退出循环，这样会少运行很多次kruskal。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5;
const int W=6e3+5;
int n,w;int fa[N],ans[W];
struct node{
    int u,v,w,p;
    bool operator< (const node &x)const{
        return w<x.w;
    }
}a[W];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int kruskal(int x){
    int res=0,cnt=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=w;i++){
        if(a[i].p>x)continue;
        int fu=find(a[i].u),fv=find(a[i].v);
        if(fu==fv)continue;
        fa[fu]=fv;
        res+=a[i].w;
        if(++cnt==n-1)return res;
    }
    return -1;
}
int main(){
    scanf("%d%d",&n,&w);
    for(int i=1;i<=w;i++){
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
        a[i].p=i;
        ans[i]=-1;
    }
    sort(a+1,a+w+1);
    for(int i=w;i>=1;i--){
        ans[i]=kruskal(i);
        if(ans[i]==-1)break;
    }
    for(int i=1;i<=w;i++)printf("%d\n",ans[i]);
    return 0;
}