问?!
查看原帖
问?!
546730
billtun楼主2024/8/9 08:30

为什么不能枚举树根,然后写一个 KRUSKAL(最小生成树),只需要传参多传一个到这里的节点个数?

#include <bits/stdc++.h>
#define int long long
#define Maxn 15

using namespace std;

int n, m, a, b, len, minl;
vector<pair<int, int> > v[Maxn];
bool vis[Maxn];
struct Edge {
	int to, lgh, num;
	bool operator <(const Edge &a) const {
		return (a.lgh * a.num) < (lgh * num);
	}
} p; priority_queue<Edge> q;
map<pair<int, int>, int> mp;
map<pair<int, int>, bool> viss;

int kruskal(int st) {
	memset(vis, 0, sizeof vis);
	int cst = 0, x = 0, lgh = 0, num = 0;
	vis[st] = 1;
	for (int i = 0; i < (int)v[st].size(); i ++) {
		int to = v[st][i].first;
		p.to = to, p.num = 1, p.lgh = v[st][i].second;
		q.push(p);
	}
	
	while (!q.empty()) {
		p = q.top(), q.pop();
		x = p.to, lgh = p.lgh, num = p.num;
		if (vis[x]) { continue; }
		vis[x] = 1, cst += (lgh * num);
//		cout << st << " : " << x << " -- " << lgh << " " << num << " Cost : " << cst << "\n";
		
		for (int i = 0; i < (int)v[x].size(); i ++) {
			int to = v[x][i].first;
			p.to = to, p.lgh = v[x][i].second, p.num = num + 1;
			q.push(p);
		}
	} return cst;
}

int solve(int x) {
	return kruskal(x);
}

signed main() {
//	freopen("E1.in", "r", stdin);
//	freopen("Mine.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> a >> b >> len;
		if (viss[make_pair(min(a, b), max(a, b))]) {
			mp[make_pair(min(a, b), max(a, b))] = min(len, mp[make_pair(min(a, b), max(a, b))]);
		} else {
			viss[make_pair(min(a, b), max(a, b))] = 1;
			mp[make_pair(min(a, b), max(a, b))] = len;
		}
//		v[a].push_back(make_pair(b, len));
//		v[b].push_back(make_pair(a, len));
	}
	
	for (int i = 1; i <= n; i ++) {
		for (int j = i; j <= n; j ++) {
			if (viss[make_pair(i, j)]) {
				v[i].push_back(make_pair(j, mp[make_pair(i, j)]));
				v[j].push_back(make_pair(i, mp[make_pair(i, j)]));
			}
		}
	}
	
	minl = 9223372036854775807;
	for (int i = 1; i <= n; i ++) {
		minl = min(minl, solve(i));
	} cout << minl;
	return 0;
}
2024/8/9 08:30
加载中...