洛谷 P1195 【口袋的天空】

P1195

传送门

大体题意：

就是给你\(n\)个点\(m\)条边， 然后让你把这几个点连成\(k\)个部分.

解题思路：

很容易就可以想到生成树(别问我怎么想到的).

因为最小生成树中有一个判断

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

		if (father(ka[i].x) != father(ka[i].y)){

			unionn(ka[i].x, ka[i].y);

			tot += ka[i].v;

			s++;

		}

		if (s == n - 1) break;//我在这里，如果这张图中已经加入了n-1条边，

	}//那就说明图已经可以联通了，然后如果去掉m条边的话，那就是把图分成了m个部分

	//那么我们可以利用这一点来用kruskal做这道题聊.

修改后的代码长这样：

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

		if (father(ka[i].x) != father(ka[i].y)){

			unionn(ka[i].x, ka[i].y);

			tot += ka[i].v;

			s++;

		}

		if (s == n - k) break;//k为分成多少个部分，自己想一下也很好想.

		//n-1条边可以把图刚刚好联通，n-k条边可以将图分成k个部分.

	}

code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iomanip>

using namespace std;

int n, m, k, s, cnt, tot;

struct node {

	int x, y, v;

}ka[200001];

int fat[5001];

int read() {

	int s = 0, f = 0; char ch = getchar();

	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();

	return f ? -s : s;

}

int father(int x) {

	if (fat[x] != x) fat[x] = father(fat[x]);//并查集用

	return fat[x];

}

void unionn(int x, int y) {//并查集用

	int fa = father(x);

	int fb = father(y);

	if (fa != fb) fat[fa] = fb;

}

bool cmp(node a, node b) {//sort用

	return a.v < b.v;

}

int main() {

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

	int x, y, d;

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

		x = read(), y = read(), d = read();

		ka[++cnt].v = d;

		ka[cnt].x = x;

		ka[cnt].y = y;

	}

	for (int i = 1; i <= n; i++) fat[i] = i;//并查集用

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

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

		if (father(ka[i].x) != father(ka[i].y)){

			unionn(ka[i].x, ka[i].y);

			tot += ka[i].v;

			s++;

		}

		if (s == n - k) break;

	}

	printf("%d\n", tot);

}