社区讨论

本题是否数据过水

LLoyalSoldier
P14362[CSP-S 2025] 道路修复参与者 2已保存回复 5

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mjctnjm8
此快照首次捕获于
2025/12/19 20:04
2 个月前
此快照最后确认于
2025/12/19 20:30
2 个月前
查看原帖
我的暴力代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+15;
const int N=1e4;
struct node{
	int x,y,z;
};
node g[maxn];
node g2[maxn];
int cnt=0;
int n,m,k;
int cost[15][N];
int c[maxn];
bool vis2[maxn];
int tmp[maxn];
long long mini=1e18;
bool vis[N];
int fa[N+15];
bool cmp(node q,node h){
	return q.z<h.z;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x){
	if(x>k){
		cnt=0;
		long long sum=0;
		for(int i=1;i<=n;i++){
			fa[i]=i;
			vis2[i]=0;
		}
		for(int i=1;i<=m;i++){
			g2[++cnt]=g[i];
		}
		for(int i=1;i<=k;i++){
			if(vis[i]){
				fa[i+n]=i+n;
				sum+=c[i];
				for(int j=1;j<=n;j++){
					g2[++cnt]={i+n,j,cost[i][j]};
				}
			}
		}
		sort(g2+1,g2+1+cnt,cmp);
		int need=n;
        int ans=0;
		for(int i=1;i<=cnt;i++){
			if(ans==n){
				break;
			}
			int xx=g2[i].x;
			int yy=g2[i].y;
			xx=find(xx);
			yy=find(yy);
			if(xx!=yy){
				if(g2[i].x<=n&&!vis2[g2[i].x]){
					vis2[g2[i].x]=true;
					ans++;
				}
				if(g2[i].y<=n&&!vis2[g2[i].y]){
					vis2[g2[i].y]=true;
					ans++;
				}
                fa[xx]=yy; 
				sum+=g2[i].z;
		    }
		}
		if(ans!=n){
			return ;
		} 
		mini=min(mini,sum);
		return ;
	}
	vis[x]=false;
	dfs(x+1);
	
	vis[x]=true;
	dfs(x+1);
	vis[x]=false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[i]={x,y,z};
	}
	sort(g+1,g+1+m,cmp);
	for(int i=1;i<=k;i++){
		cin>>c[i];
		for(int j=1;j<=n;j++){
			cin>>cost[i][j];
		}
	}
	dfs(1);
	cout<<mini;
	return 0;
}
本来没啥搞头，就是个死暴力。但是容易发现每次都sort，烦死了。于是直接在输入后统一 sort。最后在 DFS 看 左右两个点是否被选即可。于是我写出了：
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+15;
const int N=1e4;
struct node{
	int x,y,z;
};
node g[maxn];
node g2[maxn];
int cnt=0;
int n,m,k;
int cost[15][N];
int c[maxn];
bool vis2[maxn];
int tmp[maxn];
long long mini=1e18;
bool vis[N];
int fa[N+15];
bool cmp(node q,node h){
	return q.z<h.z;
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x){
	if(x>k){
		cnt=0;
		long long sum=0;
		for(int i=1;i<=n;i++){
			fa[i]=i;
			vis2[i]=0;
		}
		for(int i=1;i<=m;i++){
			g2[++cnt]=g[i];
		}
		for(int i=1;i<=k;i++){
			if(vis[i]){
				fa[i+n]=i+n;
				sum+=c[i];
				for(int j=1;j<=n;j++){
					g2[++cnt]={i+n,j,cost[i][j]};
				}
			}
		}
		sort(g2+1,g2+1+cnt,cmp);
		int need=n;
        int ans=0;
		for(int i=1;i<=cnt;i++){
			if(ans==n){
				break;
			}
			int xx=g2[i].x;
			int yy=g2[i].y;
			xx=find(xx);
			yy=find(yy);
			if(xx!=yy){
				if(g2[i].x<=n&&!vis2[g2[i].x]){
					vis2[g2[i].x]=true;
					ans++;
				}
				if(g2[i].y<=n&&!vis2[g2[i].y]){
					vis2[g2[i].y]=true;
					ans++;
				}
                fa[xx]=yy; 
				sum+=g2[i].z;
		    }
		}
		if(ans!=n){
			return ;
		} 
		mini=min(mini,sum);
		return ;
	}
	vis[x]=false;
	dfs(x+1);
	
	vis[x]=true;
	dfs(x+1);
	vis[x]=false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[i]={x,y,z};
	}
	sort(g+1,g+1+m,cmp);
	for(int i=1;i<=k;i++){
		cin>>c[i];
		for(int j=1;j<=n;j++){
			cin>>cost[i][j];
		}
	}
	dfs(1);
	cout<<mini;
	return 0;
}
结果 AC 了。 最大耗时 1.13s。前20个点均<=260ms。这暴力加个优化就过了。是题解（大众）搞复杂了还是我想错了

回复

共 5 条回复，欢迎继续交流。

正在加载回复...