Solution-P14362

讲一讲自己的考场思路。

首先发现题目中有“任意两座城市都能通过若干条道路相互到达。”这样一句话，说明我们大概率需要求出原图最小生成树。求出原图最小生成树后，你会发现其他边无论如何都是没用的，因此我们把边数缩减到了

n-1

。

然后我们发现

k\le10

，这允许我们

O(2^k)

枚举对哪些乡镇进行城市化改造，结合把这些边加进原图的最小生成树后再求最小生成树即可。时间复杂度

O(m\log m+2^kkn\log n)

。

复杂度带一只

\log

不知道能不能过，所以尝试优化。我们先对每个乡镇连出的

n

条边按边权从小到大排序，然后由于原图最小生成树的边也是按边权从小到大排序的，我们相当于需要合并

k+1

个有序数列，归并即可。时间复杂度

O(m\log m+kn\log n+2^kk^2n\alpha(n))

，但是跑不满，可以优化归并的部分做到把

k^2

去掉。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}p[1000001],t[10001],a[11][10001],h[1000001],tmp[1000001];
int n,m,k,f[10011],c[11],cnt,siz,x,y;
long long res,ans;
vector<int>u;
inline bool cmp(node _1,node _2){
	return _1.w<_2.w;
}
inline int find(int i){
	return f[i]==i?i:f[i]=find(f[i]);
}
inline void dfs(int i){
	if(i==k+1){
		siz=n-1;
		res=0;
		for(int j=1;j<=siz;j++){
			h[j]=t[j];
		}
		for(int j:u){
			res+=c[j];
			merge(h+1,h+siz+1,a[j]+1,a[j]+n+1,tmp+1,cmp);
			siz+=n;
			for(int l=1;l<=siz;l++){
				h[l]=tmp[l];
			}
		}
		for(int j=1;j<=n+k;j++){
			f[j]=j;
		}
		for(int j=1;j<=siz;j++){
			x=find(h[j].u);
			y=find(h[j].v);
			if(x!=y){
				f[x]=y;
				res+=h[j].w;
			}
		}
		ans=min(ans,res);
		return;
	}
	for(int j=i+1;j<=k+1;j++){
		if(j!=k+1){
			u.push_back(j);
		}
		dfs(j);
		if(j!=k+1){
			u.pop_back();
		}
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>p[i].u>>p[i].v>>p[i].w;
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	sort(p+1,p+m+1,cmp);
	for(int i=1;i<=m;i++){
		x=find(p[i].u);
		y=find(p[i].v);
		if(x!=y){
			f[x]=y;
			cnt++;
			t[cnt]=p[i];
			ans+=p[i].w;
		}
	}
	for(int i=1;i<=k;i++){
		cin>>c[i];
		for(int j=1;j<=n;j++){
			cin>>a[i][j].w;
			a[i][j].u=n+i;
			a[i][j].v=j;
		}
		sort(a[i]+1,a[i]+n+1,cmp);
	}
	dfs(0);
	cout<<ans;
	return 0;
}

文章操作

相关推荐

评论

Solution-P14362