September Cook-Off 2012 COALSCAM : Coal Scam

問題概要

辺が与えられる。辺にはコストとAまたはBの属性がある。全域木をつくって、Bに属するコストを最大化し、そのなかで全コストの和を最小化したい。それぞれの値を求める問題。

解法

ただの最小全域木。

acceptされたコード

const int MAX_M = 40000;

int N, M1, M2;
pair< pair<int64,int64>, pair<int, int> > es[MAX_M];

void init() {
	scanf("%d%d%d", &N, &M1, &M2);
	for (int i = 0; i < M1; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		es[i] = make_pair(make_pair(0, z), make_pair(x, y) );
	}
	for (int i = 0; i < M2; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		es[i+M1] = make_pair(make_pair(-z, z), make_pair(x, y));
	}
}

void solve() {
	int cnt = 0;
	uf.init(N);
	sort(es, es + M1 + M2);
	int64 ans1 = 0, ans2 = 0;
	for (int i = 0; i < M1 + M2; ++i) {
		int x = es[i].second.first, y = es[i].second.second;
		if (!uf.isSame(x, y)) {
			++cnt;
			uf.merge(x, y);
			ans1 -= es[i].first.first;
			ans2 += es[i].first.second;
		}
	}

	if (cnt == N - 1) {
		printf("%lld %lld\n", ans1, ans2);
	}
	else {
		puts("Impossible");
	}
}