楽しすぎる家庭菜園 [いろはちゃんコンテスト Day2 D]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_d

前提知識

• 最小全域木

解説

https://atcoder.jp/contests/iroha2019-day2/submissions/5214486

これは一般的な話だが、ある問題を見たときに今まで解いた類題が思い出せれば、
そこから似たような考え方を輸入して、問題の解法を導けることがよくある。
今回の問題であれば「最小全域木」である。
　
水の量を全てマイナスにして考えると今回の問題は最小全域木と全く同じになる。
クラスカル法を使って解こう。
最小全域木とは違って、辺のコストが大きい順でソートして、UnionFindで連結であるかどうかを見ながら、
連結でないなら、採用してくっつけていく。
最小全域木の方を先に学習するといいかもしれない。

int N, M;
int A[401010], B[401010], C[401010];
vector<pair<int, int>> E;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		cin >> A[i] >> B[i] >> C[i];
		E.push_back({ C[i], i });
	}
	sort(all(E), greater<pair<int, int>>());
 
	vector<int> ans;
	UnionFind uf(N + 1);
	fore(p, E) {
		int cst = p.first;
		int i = p.second;
		int a = A[i];
		int b = B[i];
 
		if (uf[a] != uf[b]) {
			uf(a, b);
			ans.push_back(i);
		}
	}
	
	sort(all(ans));
	fore(x, ans) printf("%d\n", x + 1);
}