fzu 1963 交通建设(kruskal)

题目链接：fzu 1963 1963 交通建设

题目大意：略。

解题思路：kruskal的变形，外填一个汇点0，将建造飞机场看成是于0点建立一条边，费用为一个飞机场的价格。然后就是裸的kruskal算法，不过要注意的是如果只有一个点与0点相连，那么就要判断该点的飞机场是否为必须建立的，如果不为必须建立的则要减掉。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

using namespace std;
const int N = 1005;
const int M = 15005;
typedef long long ll;

struct line {
	int u, v;
	ll l;
}way[M];

ll ans, costA, costB;
int n, m, k, t, cnt, f[N];

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

bool cmp (const line& a, const line& b) {
	return a.l < b.l;
}

void init () {
	int a;
	ll b;

	cin >> costA >> costB;

	cnt = ans = 0;
	for (int i = 0; i <= n; i++)
		f[i] = i;

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &way[i].u, &way[i].v);
		cin >> b;
		way[i].l = b * costB;
	}

	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		scanf("%d", &a);
		f[get(a)] = 0;
		ans += costA;
	}

	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		scanf("%d", &a);
		--a;

		int p = get(way[a].u);
		int q = get(way[a].v);
		ans += way[a].l;

		if (p != q)
			f[p] = q;
	}

	for (int i = 1; i <= n; i++) {
		way[m].u = i;
		way[m].v = 0;
		way[m].l = costA;
		m++;
	}

	sort (way, way + m, cmp);
}

ll solve () {
	for (int i = 0; i < m; i++) {
		int p = get(way[i].u);
		int q = get(way[i].v);

		if (p != q) {
			ans += way[i].l;
			f[p] = q;
			if (q == 0) cnt++;
		}
	}

	return ans - (cnt == 1  && k == 0 ? costA : 0);
}

int main () {
	while (scanf("%d%d", &n, &m) == 2) {
		init ();
		cout << solve () << endl;
	}
	return 0;
}

fzu 1963 交通建设(kruskal),布布扣,bubuko.com

fzu 1963 交通建设(kruskal)

原文：http://blog.csdn.net/keshuai19940722/article/details/22512937