克鲁斯卡尔重构树

发现没把板子放上来... 现在放一下

克鲁斯卡尔算法的正确性是利用反证法证明的. 简要地说, 就是如果不加入当前权值最小的边 \(e_1\), 那么之后加入的边和这条边会形成一个环. 去掉这个环上权值最大的边 \(e_2\) 并加入 \(e_1\), 答案不会更劣.

struct te0{int f,t,v;}e0[msz];

bool operator<(te0 a,te0 b){return a.v>b.v;}

int val[nsz*2],pd=0;

int fa[lnsz][nsz*2];

struct tdsu{

	int fa[nsz*2];

	void init(){rep(i,1,n*2)fa[i]=i;}

	int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);}

}dsu;

void kru(){

	pd=n;

	dsu.init();

	sort(e0+1,e0+m+1);

	rep(i,1,n)val[i]=ninf;

	rep(i,1,m){

		int x=dsu.find(e0[i].f),y=dsu.find(e0[i].t);

		if(x==y)continue;

		++pd;

		dsu.fa[x]=dsu.fa[y]=pd;

		val[pd]=e0[i].v;

		fa[0][x]=fa[0][y]=pd;

	}

}