社区讨论

这样写有问题吗

P14362[CSP-S 2025] 道路修复参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhphu1en
此快照首次捕获于
2025/11/08 07:35
4 个月前
此快照最后确认于
2025/11/09 02:26
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm = 1e6 + 10,maxn = 1e5 + 10;
int read() {
	int cc = 0,ccc = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') {
			ccc *= -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		cc = cc * 10 + c - '0';
		c = getchar(); 
	}
	return cc * ccc;
}
struct node {
	int u,v,w;
}road[maxm],edge[maxn];
bool compare(node a,node b){
    return a.w < b.w;
}
int fa[maxn],c[11];
int find(int x) {
	if(fa[x] == x) {
		return x;
	}
	else {
		return fa[x] = find(fa[x]);
	}
}
int n,m,k;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	n = read();
	m = read();
	k = read();
	for (int i = 1; i <= n + k; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		road[i].u = read();
		road[i].v = read();
		road[i].w = read();
	}
	sort(road + 1,road + m + 1,compare);
	int ans = 0,cnt = 0;
	for (int i = 1; i <= m; i++) {
		int u = road[i].u;
		int v = road[i].v;
		u = find(u),v = find(v);
		if(u == v) {
			continue;
		}
		cnt++;
		edge[cnt].u = u;
		edge[cnt].v = v;
		edge[cnt].w = road[i].w;
		ans += road[i].w;
		fa[u] = v;
		if(cnt == n - 1) {
			break;
		}
	}
	if(k == 0) {
		cout << ans << "\n";
		return 0;
	}
	for (int i = 1; i <= k; i++) {
		c[i] = read();
		for (int j = 1; j <= n; j++) {
            road[n + (i - 1) * n + j].u = n + i;
			road[n + (i - 1) * n + j].v = j;
			road[n + (i - 1) * n + j].w = read();
		}
	}
	for (int i = 1; i < (1 << k); i++) {
		for (int j = 1; j <= n + k; j++) {
			fa[j] = j;
		}
		int sum = 0,now = 0,num = 0;
		cnt = n - 1;
		for (int j = 0; j < k; j++) {
			if(i & (1 << j)) {
				num++;
				sum += c[j + 1];
				for (int l = 1; l <= n; l++) {
					edge[++cnt].u = road[n + j * n + l].u;
					edge[cnt].v = road[n + j * n + l].v;
					edge[cnt].w = road[n + j * n + l].w;
				}
			}
		}
		sort(edge + 1,edge + cnt + 1,compare);
		for (int j = 1; j <= cnt; j++) {
			int u = edge[j].u;
			int v = edge[j].v;
			u = find(u),v = find(v);
			if(u == v) {
				continue;
			}
			sum += edge[j].w;
			now++;
			fa[v] = u;
			if(now == n + num - 1) {
				break;
			}
		}
//		cout << ans << " " << sum << "\n";
		ans = min(ans,sum);
	}
	cout << ans << "\n";
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...