题目

链接

https://www.luogu.com.cn/problem/CF1245D

字面描述

题面翻译

已知一个平面上有 n n n 个城市，需要个 n n n 个城市均通上电

一个城市有电，必须在这个城市有发电站或者和一个有电的城市用电缆相连

在一个城市建造发电站的代价是 c [ i ] c[i] c[i]

i i i 和 j j j 两个城市相连的代价是 k [ i ] + k [ j ] k[i]+k[j] k[i]+k[j] 乘上两者的曼哈顿距离

求最小代价的方案

输入:

第一行为城市个数

下面是每个城市的坐标 x [ i ] 和 y [ i ] x[i]和y[i] x[i]和y[i]

下面是建造发电站的代价 c [ i ] c[i] c[i]

下面是每个城市连线的系数 k [ i ] k[i] k[i]

输出:

一个为最小代价

建造发电站的城市数，和每个城市

连线的条数，和每条连线

任意一种即可，输出顺序任意

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

For the answers given in the samples, refer to the following diagrams (cities with power stations are colored green, other cities are colored blue, and wires are colored red):

CF1245D Shichikuji and Power Grid 题解-LMLPHP

For the first example, the cost of building power stations in all cities is 3 + 2 + 3 = 8 3 + 2 + 3 = 8 3+2+3=8 . It can be shown that no configuration costs less than 8 yen.

For the second example, the cost of building a power station in City 2 is 2. The cost of connecting City 1 and City 2 is 2 ⋅ ( 3 + 2 ) = 10 2 \cdot (3 + 2) = 10 2⋅(3+2)=10 . The cost of connecting City 2 and City 3 is 3 ⋅ ( 2 + 3 ) = 15 3 \cdot (2 + 3) = 15 3⋅(2+3)=15 . Thus the total cost is 2 + 10 + 15 = 27 2 + 10 + 15 = 27 2+10+15=27 . It can be shown that no configuration costs less than 27 yen.

思路点拨

求全图连接的最小距离，无意（可能也是友善的出题人有意)的透漏了本题是一道最小生成树。
但无非的差别是，图内必须有一点连接核电站，这个处理起来十分简单，只需要建一个虚拟原点0号节点， 0 号节点到 i 号节点的有向边的权值为 c i 0号节点到i号节点的有向边的权值为c_i 0号节点到i号节点的有向边的权值为ci
之后在把其他 ∀ i 与 ∀ j ( 1 ≤ i ≤ n ) ( 1 ≤ j ≤ n ) ( i = / j ) , 一一建边权为 ( ∣ x i − x j ∣ + ∣ y i − y j ∣ ) ⋅ ( k i + k j ) 的有向边 \forall i与\forall j (1 \leq i \leq n) (1 \leq j \leq n)(i{=}\mathllap{/\,}j),一一建边权为(|x_i-x_j|+|y_i-y_j|)\cdot(k_i+k_j)的有向边 ∀i与∀j(1≤i≤n)(1≤j≤n)(i=/j),一一建边权为(∣xi−xj∣+∣yi−yj∣)⋅(ki+kj)的有向边
切记记得开 l o n g long long l o n g long long（不同意的自己去算范围
时间复杂度: O ( n 2 ⋅ l o g 2 ( n 2 ) ) ≈ 2 e 7 \Omicron (n^2\cdot log2(n^2))\approx 2e7 O(n2⋅log2(n2))≈2e7
AC
分析结束！

代码实现

//收获虚拟原点 
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e3+10;
int n,cnt,ans=0,tot1,tot2,n1; 
int c[maxn],k[maxn],fa[maxn];
bool use[maxn];
struct node{
	int x,y;
	inline void input(){
		scanf("%d%d",&x,&y);
	}
}a[maxn];
struct vertex{
	int x,y,w;
	bool vis;
}e[maxn*maxn];
inline int distance(int x1,int y1,int x2,int y2){return abs(x1-x2)+abs(y1-y2);}
inline bool cmp(vertex nx,vertex ny){return nx.w<ny.w;}
inline int find(int nx){
	if(nx==fa[nx])return nx;
	return fa[nx]=find(fa[nx]);
}
inline bool merge(int nx,int ny){
	int p=find(fa[nx]);
	int q=find(fa[ny]);
	if(p==q)return false;
	fa[p]=q;
	return true;
}
inline void Kruskal(){
	sort(e+1,e+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		if(merge(e[i].x,e[i].y)){
			ans+=e[i].w;
			if(e[i].x==0){
				++tot1;
				use[e[i].y]=true;
			}
			else {
				e[i].vis=true; 
				++tot2;	
			}
			n--;
			if(n==1)return;
		}
	}
}
inline void Print(){
	printf("%lld\n",ans);
	printf("%lld\n",tot1);
	for(int i=1;i<=n1;i++){
		if(use[i])printf("%lld ",i);
	}
	printf("\n");
	printf("%lld\n",tot2);
	for(int i=1;i<=cnt;i++){
		if(e[i].vis)printf("%lld %lld\n",e[i].x,e[i].y);
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)a[i].input();
	for(int i=1;i<=n;i++){
		scanf("%lld",&c[i]);
		e[++cnt].x=0;
		e[cnt].y=i;
		e[cnt].w=c[i]; 
	}
	for(int i=1;i<=n;i++)scanf("%lld",&k[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			e[++cnt].x=i;
			e[cnt].y=j;
			int dis=distance(a[i].x,a[i].y,a[j].x,a[j].y);
			e[cnt].w=(k[i]+k[j])*dis;
		}
	}
	for(int i=0;i<=n;i++)fa[i]=i;
	++n;
	n1=n-1;
	Kruskal();
	Print();
	return 0;
}

sbj_ssfer_noier

CF1245D Shichikuji and Power Grid 题解