题解：P9926 [NFLSPC #6] 所以 k 小生成树怎么做？

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 1000000007
#define ld long double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,val)memset(x,val,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
//#define D(i,j,n)for(int i=j;i>=n;i--)
//#define E(i,now)for(int i=first[now];i;i=e[i].nxt)
//#define F(i,j,n)for(int i=j;i<=n;i++)
//#define DL(i,j,n)for(register ll i=j;i>=n;i--)
//#define EL(i,now)for(register ll i=first[now];i;i=e[i].nxt)
//#define FL(i,j,n)for(register ll i=j;i<=n;i++)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1e5+5;
const i64 oo = 1e18;

i64 n,m,k,tot;
struct edge{i64 u,v,w;}a[maxn];
bool operator<(const edge&A,const edge&B){
	return A.w<B.w;
}
struct dsu{
	i64 fa[maxn];
	IV init(){F(i,0,n-1)fa[i]=i;}
	i64 find(i64 x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	IV merge(i64 x,i64 y){x=find(x);y=find(y);fa[y]=x;}
}tr;
struct dat{
	i64 del,add,from,val;
	bool operator<(const dat&z)const{
		return val>z.val;
	}
};
struct node{
	i64 dft,val;
	vector<vector<i64> >e;
	vector<i64>st,fa,dfn,siz,lab;
	IV dfs(i64 x,i64 F){
		fa[x]=F;dfn[x]=++dft;siz[x]=1;
		for(i64 i:e[x])if(i!=F)dfs(i,x),siz[x]+=siz[i];
	}
	bool anc(i64 x,i64 y){return dfn[x]<=dfn[y]&&dfn[x]+siz[x]>dfn[y];}
	IV init(){
		fa.resize(n);dfn.resize(n);
		siz.resize(n);lab.resize(n);

		dfs(0,0);
		F(i,0,m-1)if(st[i]&1){
			i64 u=::a[i].u,v=::a[i].v;
			if(anc(v,u))swap(u,v);lab[v]=i;
		}
	}
	dat suc(){
		tr.init();
		i64 del=-1,add=-1,dlt=oo;
		F(i,0,m-1){
			if(st[i])continue;
			i64 u=a[i].u,v=a[i].v;
			F(kkk,1,2){
				while(1){
					u=tr.find(u);
					if(anc(u,v))break;tr.merge(fa[u],u);
					i64 x=lab[u],dltx=a[i].w-a[x].w;
					// cout<<i<<' '<<x<<endl;
					if(st[x]==3)dltx=oo;
					if(dltx<dlt)dlt=dltx,del=x,add=i;
				}
				u=a[i].u,swap(u,v);
			}
		}
		// cout<<dlt<<endl;
		return{del,add,-1,dlt};
	}
}mst;
vector<node>st;
IV init(){
	st.resize(k);mst.st.resize(m);
	mst.e.resize(n,vector<i64>());tr.init();
	F(i,0,m-1){
		i64 u=tr.find(a[i].u),v=tr.find(a[i].v);
		if(u!=v){
			mst.st[i]=1;mst.val+=a[i].w;
			mst.e[a[i].u].push_back(a[i].v);
			mst.e[a[i].v].push_back(a[i].u);
			tr.merge(u,v);
		}
	}
}
IV kmst(){
	priority_queue<dat>q;
	q.push({-1,-1,-1,mst.val});
	i64 id=0;
	while(k&&!q.empty()){
		dat t=q.top();q.pop();
		printf("%lld\n",t.val);k--;
		// puts("?");
		node&z=st[id];
		if(t.from==-1)z=mst;
		else{
			z=st[t.from];z.dft=0;z.val=t.val;
			i64 u=a[t.del].u,v=a[t.del].v;
			z.e[u].erase(find(z.e[u].begin(),z.e[u].end(),v));
			z.e[v].erase(find(z.e[v].begin(),z.e[v].end(),u));
			u=a[t.add].u,v=a[t.add].v;
			z.e[u].push_back(v);
			z.e[v].push_back(u);
			z.st[t.del]=0,z.st[t.add]=3;
			st[t.from].st[t.add]=2;
			dat res=st[t.from].suc();
			res.from=t.from;
			// cout<<res.val<<endl;
			res.val+=st[t.from].val;
			if(res.add!=-1)q.push(res);
		}
		z.init();
		dat res=z.suc();
		res.from=id,res.val+=t.val;
		if(res.add!=-1)q.push(res);
		id++;
	}
	while(k--)puts("-1");
}
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	n=read();m=read();k=read();
	F(i,0,m-1){
		a[i].u=read();a[i].v=read();a[i].w=read();
		a[i].u--;a[i].v--;
	}
	sort(a,a+m);
	init();kmst();
	return 0;
}