白駿

質問リンク

https://www.acmicpc.net/problem/20010

質問する

に答える

クルーズアルゴリズムを使用して最小伸長ツリー

を作成

の最小伸長ツリーを作成すると、最小伸長ツリーの接続情報がリンク配列に格納される

.

最小伸長木が完成すると、村間接続情報から最大のコストを得るために、dfsブラウズリンク配列

を通過する.

dfsナビゲーション時に、各端末ノードを始点として位置決めし、その後、ナビゲーション

を開始する.

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
int parents[1001];
vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> linked[1001];

void init() {
	for (int i = 0; i < 1001; i++) parents[i] = i;
}

int find_parents(int x) {
	if (parents[x] == x) return x;
	else return parents[x] = find_parents(parents[x]);
}

int union_parents(int a, int b) {
	int p1 = find_parents(a);
	int p2 = find_parents(b);
	if (p1 != p2) {
		parents[p1] = p2;
		return 1;
	}
	return 0;
}

int find_max2(int start, int before, int max_cost) {
	int ans = 0;
	for (int i = 0; i < linked[start].size(); i++) {
		if (linked[start][i].second == before) continue;
		ans = max(ans, find_max2(linked[start][i].second, start, max_cost + linked[start][i].first));
	}
	ans = max(ans, max_cost);
	return ans;
}

int find_max() {
	int max_cost = 0;
	for (int i = 0; i < n; i++) {
		if (linked[i].size() == 1) {
			max_cost = max(max_cost, find_max2(i, -1, 0));
		}
	}
	return max_cost;
}

int make_mst() {
	int mst_sum = 0;
	for (int i = 0; i < v.size(); i++) {
		int cost = v[i].first;
		int a = v[i].second.first;
		int b = v[i].second.second;
		if (union_parents(a, b)) {
			mst_sum += cost;
			linked[a].push_back({ cost,b });
			linked[b].push_back({ cost,a });
		}
	}
	return mst_sum;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	init();

	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		v.push_back({ cost,{a,b} });
	}
	sort(v.begin(), v.end());
	cout << make_mst() << '\n';
	cout << find_max();
}

ポスト

おなじみのアルゴリズムなので難しくはありませんが、コードが乱れています.私たちもきれいに編む練習をしましょう.