Author: lllyouo
Date: 20250224
tag: 最新生成树、虚拟源点
link: https://www.luogu.com.cn/problem/P1194

问题描述

link

分析

考虑建图，由于既有边权又有点权，可以建立一个虚拟源点（设为 $0$ 号点）。对于点权，建立 $0$ 号点到该点的一条边，权值改为边权。

建图之后发现：一条从 $0$ 号点出发的路径就代表着以路径的边权和购买了路径上的所有物品，也即是该图的一颗生成树。为了使价格花费最低，也就是路径边权之和最低，求最小生成树即可。

参考代码

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

const int N = 510;
int n, m, p[N];

struct NODE {
	int u, v, w;
	
	bool operator < (const NODE& x) {
		return w < x.w;
	}
};
vector<NODE> e;

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

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			int k; cin >> k;
			if (k) e.push_back({i, j, k});
			else e.push_back({0, i, n});
		}
	}
	sort(e.begin(), e.end());
	for (int i = 0; i <= m; i++) p[i] = i;
	
	int ans = 0;
	for (int i = 0; i < e.size(); i++) {
		int fu = find(e[i].u);
		int fv = find(e[i].v);
		if (fu != fv) {
			p[fu] = fv;
			ans += e[i].w;
		}
	}

	cout << ans << endl;
	
	return 0;
}