[Acwing] 1143.联络员 Kruskal 必选边问题

前言

prim真的不好处理hh 传送门 :

思路

刚刚做完上题,虽然看到这题的范围是这样,但是也不敢用 p r i m prim prim处理了

如何用 k r u s k a l kruskal kruskal处理呢?

其实只是处理必选边而已

也就是我们在加边的时候就可以把必选边加进我们的集合当中 ‘ 这样子就相当于按照题目意思模拟了hh

CODE

struct Edge
{
	int a,b,w;
	bool operatorm;
	int ans = 0 ;
	init();
	for(int i=1;i>op>>a>>b>>c;
		
		if(op == 1)
		{
			a = find(a);
			b = find(b);
			ans+=c;
			p[a]=b;
		}
		else
		edge[++cnt] = {a,b,c};
	}
	
	kruskal();
	cout