白駿

質問リンク

質問する

に答える

コード#コード#

#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();
}

ポスト