洛谷P1195口袋的天空

传送门啦

一个裸的最小生成树，输出 $ No Answer $ 的情况只有 $ k < n $ 的时候。

开始令 $ num =n $ ，如果 $ num = k $ ，直接输出 $ 0 $ ，最后就是最小生成树操作了，退出的条件就是 $ num = k $ 。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1005;

const int maxm = 10005;

inline int read(){char ch = getchar();int f = 1 , x = 0;while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;}

int n,m,k,x,y,z;

int head[maxn],tot;

int f[maxn],ans;

struct Edge{

	int from,to,val,next;

}edge[maxm << 1];

inline void add(int u,int v,int w){

	edge[++tot].from = u;

	edge[tot].to = v;

	edge[tot].next = head[u];

	edge[tot].val = w;

	head[u] = tot;

}

inline int find(int x){

	if(x != f[x])  f[x] = find(f[x]);

	return f[x];

}

inline bool cmp(Edge a , Edge b){

	return a.val < b.val;

}

inline void init(){

	for(int i=1;i<=n;i++)

		f[i] = i;

}

int main(){

	n = read(); m = read(); k = read();

	if(k > n) {

		printf("No Answer");

		return 0;

	}

	for(int i=1;i<=m;i++){

		x = read(); y = read(); z = read();

		add(x , y , z);

	}

	init();

	sort(edge + 1  , edge + 1 + m , cmp);

	int num = n;

	if(num == k){

		printf("0\n");

		return 0;

	}

	for(int i=1;i<=m;i++){

		int f1 = find(edge[i].from);

		int f2 = find(edge[i].to);

		if(f1 != f2){

			f[f1] = f2;

			num--;

			ans += edge[i].val;

		}

		if(num == k)  break;

	}

	printf("%d",ans);

	return 0;

}

巴特西

洛谷P1195口袋的天空

传送门啦

最新文章

热门文章