Author: lllyouo
Date: 20250226
tag: 最小生成树、虚拟源点
link: https://www.luogu.com.cn/problem/P1550

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u, v, w;

	bool operator< (const Edge& x) {
		return w < x.w;
	}
};

vector<Edge> e;
int n, p[310];
long long ans;

int find(int x) {
	if (x == p[x]) return x;
	return p[x] = find(p[x]);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int w; cin >> w;
		e.push_back({0, i, w});
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w; cin >> w;
			if (i != j) {
				e.push_back({i, j, w});
			}
		}
	}

	for (int i = 1; i <= n; i++) p[i] = i;
	sort(e.begin(), e.end());

	for (auto x : e) {
		int fu = find(x.u);
		int fv = find(x.v);

		if (fu != fv) {
			p[fu] = fv;
			ans += x.w;
		}
	}
	cout << ans << endl;

	return 0;
}