社区讨论

求指出逻辑错误

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 条回复,欢迎继续交流。

正在加载回复...