专栏文章

[CSP-S 2025] 道路修复 / road

__H17_
P14362题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minfdxvg
此快照首次捕获于
2025/12/02 01:30
3 个月前
此快照最后确认于
2025/12/02 01:30
3 个月前
查看原文

前言

还是输在蓝题了，不过好像不是输的那么彻底，还能翻盘吗？——失败了，我怎么这么弱，被杀穿了。

题目分析

首先注意到 mm 条边中不在最小生成树里的一定没有用，这条边一定可以被其它边代替。求一遍最小生成树可以把 mm 去掉，这部分时间复杂度 O(mlog⁡m)O(m\log m)，可以使用 Kruskal。
我们对剩下 kk 个乡镇不好处理（由于不需要用的乡镇不应该加点权），考虑枚举，每次做暴力最小生成树，这部分时间复杂度是 O(2knklog⁡nk)O(2^knk\log nk)。
考虑瓶颈在哪里？——排序。整体排序即可，时间复杂度 O(mlog⁡m+2knk)O(m\log m+2^k nk)。但我没想到这个东西，所以写的是随机化暴力。

代码

先给一份随机化暴力的代码，这个不保证能通过。
CPP
#include<bits/stdc++.h>
#define int long long
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e4+11,M=1e6+1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
__inline void read(int&x){
	x=0;
	char ch=getchar();
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
		x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return;
}
void write(int x){
	if(x>=10)
		write(x/10);
	putchar((x%10)^48);
	return;
}
int n,m,k,fa[N],siz[N],ans,edcnt,cst[11],wal[11][N],st=clock(),perm[11]={0,1,2,3,4,5,6,7,8,9,10};
//vector<pair<int,int> >e[N];
vector<tuple<int,int,int> >edges,tmp;
void initdsu(int nn){
	for(int i=0;i<=nn;i++)
		fa[i]=i,siz[i]=1;
	return;
}
__inline int findfa(int x){
    int tmp=x,xx=x;
    while(fa[tmp]!=tmp)
        tmp=fa[tmp];
    while(fa[x]!=tmp)
        x=fa[x],
        fa[x]=tmp;
    return fa[xx]=tmp;
}
__inline bool cmp(const tuple<int,int,int>&a,const tuple<int,int,int>&b){
	return(get<2>(a))<(get<2>(b));
}
int kruskal(const int&cnt,const int&pt){
	int res=pt;
	edcnt=0;
	initdsu(n+k);
	sort(ALL(edges),cmp);
	for(auto ed:edges){
		int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
		if(fau!=fav){
			edcnt++;
			res+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
			fa[fau]=fav,siz[fav]+=siz[fau];
		}
		if(edcnt==n+cnt-1||res>=ans)
			break;
	}
	return res;
}
signed main(){
	read(n),read(m),read(k);
	for(int i=1,u,v,w;i<=m;i++){
		read(u),read(v),read(w);
		edges.push_back(make_tuple(u,v,w));
	}
	for(int i=1;i<=k;i++){
		read(cst[i]);
		for(int j=1;j<=n;j++)
			read(wal[i][j]);
	}
	initdsu(n);
	sort(ALL(edges),cmp);
	for(auto ed:edges){
		int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
		if(fau!=fav){
			edcnt++;
			ans+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            siz[fav]+=siz[fau];
			fa[fau]=fav;
			tmp.push_back(ed);
		}
		if(edcnt==n-1)
			break;
	}
	shuffle(perm+1,perm+k+1,rng);
	for(int s=1,res,cnt;s<(1<<k);s++){
		res=cnt=0,edges=tmp;
		for(int i=1;i<=k;i++)
			if((s>>(i-1))&1){
				int v=perm[i];
				res+=cst[v],cnt++;
				for(int j=1;j<=n;j++)
					edges.push_back(make_tuple(n+v,j,wal[v][j]));
			}
		ans=min(ans,kruskal(cnt,res));
		if(1.0*(clock()-st)/CLOCKS_PER_SEC>1.98)
			break;
	}
	write(ans);
	return 0;
}
再放一份正解代码：
CPP
#include<bits/stdc++.h>
#define int long long
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e4+11,M=1e6+1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
__inline void read(int&x){
	x=0;
	char ch=getchar();
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
		x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return;
}
void write(int x){
	if(x>=10)
		write(x/10);
	putchar((x%10)^48);
	return;
}
int n,m,k,fa[N],siz[N],ans,edcnt,cst[11],wal[11][N],st=clock(),perm[11]={0,1,2,3,4,5,6,7,8,9,10};
//vector<pair<int,int> >e[N];
vector<tuple<int,int,int> >edges,tmp;
void initdsu(int nn){
	for(int i=0;i<=nn;i++)
		fa[i]=i,siz[i]=1;
	return;
}
__inline int findfa(int x){
    int tmp=x,xx=x;
    while(fa[tmp]!=tmp)
        tmp=fa[tmp];
    while(fa[x]!=tmp)
        x=fa[x],
        fa[x]=tmp;
    return fa[xx]=tmp;
}
__inline bool cmp(const tuple<int,int,int>&a,const tuple<int,int,int>&b){
	return(get<2>(a))<(get<2>(b));
}
int kruskal(const int&cnt,const int&pt,int s){
	int res=pt;
	edcnt=0;
	initdsu(n+k);
//	sort(ALL(edges),cmp);
	for(auto ed:edges){
		int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed));
        if((u<=n||u>n&&((s>>((u-n)-1))&1))&&(v<=n||v>n&&((s>>((v-n)-1))&1)));
        else continue;
        int fau=findfa(u),fav=findfa(v);
		if(fau!=fav){
			edcnt++;
			res+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
			fa[fau]=fav,siz[fav]+=siz[fau];
		}
		if(edcnt==n+cnt-1||res>=ans)
			break;
	}
	return res;
}
signed main(){
	read(n),read(m),read(k);
	for(int i=1,u,v,w;i<=m;i++){
		read(u),read(v),read(w);
		edges.push_back(make_tuple(u,v,w));
	}
	for(int i=1;i<=k;i++){
		read(cst[i]);
		for(int j=1;j<=n;j++)
			read(wal[i][j]);
	}
	initdsu(n);
	sort(ALL(edges),cmp);
	for(auto ed:edges){
		int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
		if(fau!=fav){
			edcnt++;
			ans+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            siz[fav]+=siz[fau];
			fa[fau]=fav;
			tmp.push_back(ed);
		}
		if(edcnt==n-1)
			break;
	}
    edges=tmp;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            edges.push_back(make_tuple(n+i,j,wal[i][j]));
    sort(ALL(edges),cmp);
	for(int s=1,res,cnt;s<(1<<k);s++){
		res=cnt=0;
		for(int i=1;i<=k;i++)
			if((s>>(i-1))&1)
				res+=cst[i],cnt++;
		ans=min(ans,kruskal(cnt,res,s));
	}
	write(ans);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...