社区讨论
求指出逻辑错误
P14362[CSP-S 2025] 道路修复参与者 1已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @miheqwbr
- 此快照首次捕获于
- 2025/11/27 20:26 3 个月前
- 此快照最后确认于
- 2025/11/28 22:50 3 个月前
48分
CPP#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[15],fa[10099];
struct node{
long long u,v,w;
}mp[19990009];
bool cmp(node a,node b){
return a.w<b.w;
}
long long find(long long x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void init(){
for(long long i=1;i<=n+k;i++){
fa[i]=i;
}
return;
}
long long ksl(long long now){
long long ans=0;
// cout<<now<<'\n';
for(long long i=0;i<k;i++){
if(now>>(i)&1)ans+=a[i];
}
for(long long i=1;i<=m+k*n;i++){
long long ra=find(mp[i].u),rb=find(mp[i].v);
if(ra!=rb){
if(ra>n&&!((now>>(ra-n))&1)){
continue;
}
fa[ra]=rb;
ans+=mp[i].w;
// cout<<mp[i].u<<' '<<mp[i].v<<' '<<mp[i].w<<'\n';
}
}
return ans;
}
void solve(){
long long ans=INT_MAX*pow(2,29);
sort(mp+1,mp+1+m+n*k,cmp);
// for(long long i=1;i<=m+k*n;i++){
// cout<<mp[i].u<<' '<<mp[i].v<<' '<<mp[i].w<<'\n';
// }
for(long long i=0;i<pow(2,k);i++){
init();
ans=min(ans,ksl(i));
}
cout<<ans;
}
int main(){freopen("P14362_5.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k;
for(long long i=1;i<=m;i++){
long long u,v,w;
cin>>u>>v>>w;
mp[i]=(node){u,v,w};
// cout<<i<<' '<<mp[i].u<<' '<<mp[i].v<<' '<<mp[i].w<<'\n';
}
for(long long i=1;i<=k;i++){
cin>>a[i];
for(long long j=1;j<=n;j++){
long long w;
cin>>w;
mp[m+i*n-n+j]=(node){i+n,j,w};
// cout<<m+i*n-n+j<<' '<<mp[m+i*n-n+j].u<<' '<<mp[m+i*n-n+j].v<<' '<<mp[m+i*n-n+j].w<<'\n';
}
}
solve();
}
/*
4 5 0
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
*/
时间优化我会自己写
回复
共 2 条回复,欢迎继续交流。
正在加载回复...