Review: 9-13 July

9 July

并查集

int fa[];

for (int i=1; i<=n; ++i) fa[i]=i;

int f(int x){return fa[x]==x?x:fa[x]=f(fa[x]);}

void join(int x,int y) {x=f(x),y=f(y); f[x]=y;}

最小生成树

边从小到大添加，共 \(n-1\) 条。统计边权和。

P1195 口袋的天空:

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

using namespace std;

int n, m, K, cnt, fa[1003], sum;

struct node{int x,y,w;

	bool operator <(const node&a)const{return w>a.w;}

};

priority_queue<node> G;

int fi(int x) {return fa[x]==x?x:fa[x]=fi(fa[x]); }

void join(int x,int y){fa[fi(x)]=fi(y);}

int main() {

	scanf("%d%d%d", &n, &m, &K);

	while (m--) {

		int a,b,c;scanf("%d%d%d", &a,&b,&c);

		G.push((node){a,b,c});

	}

	for (int i=1; i<=n; ++i) fa[i]=i;cnt=n;

	while (!G.empty()){

		node a=G.top();G.pop();

		if (fi(a.x)!=fi(a.y)) join(a.x,a.y),sum+=a.w,--cnt;

		if (cnt==K)break;

	}

	if (cnt!=K) printf("No Answer\n");

	else printf("%d\n", sum);

	return 0;

}

巴特西

Review: 9-13 July

9 July

并查集

最小生成树

13 July

Review

最新文章

热门文章