社区讨论
这样写有问题吗
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 条回复,欢迎继续交流。
正在加载回复...