Codeforces Round 597 (Div. 2) D （最小生成树）

题目链接：Codeforces Round 597 (Div. 2) D

// Problem: D. Shichikuji and Power Grid
// Contest: Codeforces - Codeforces Round 597 (Div. 2)
// URL: https://codeforces.com/contest/1245/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int N=2e5+5;
const int M=N*2;
const int P=1e6;
 
struct edge{   
	int sx,sy,ex,ey;
	ll w;
};
 
vector<int> p;
vector<edge> v;
 
int find(int x){    //并查集
	if(p[x]!=x){
		p[x]=find(p[x]);
	}
	return p[x];
}
 
void add(int sx,int sy,int ex,int ey,ll w){   //建树，分别是两个点的坐标和边值
	v.push_back({sx,sy,ex,ey,w});
}
 
bool cmp(edge a,edge b){   //按边值排序
	return a.w<b.w;
}
 
int main(){
	int n;
	cin>>n;
	
	vector<int> x(n+1),y(n+1);   //坐标
	map<ll,int> mp;   //离散化
	mp[0]=0;
	map<pii,int> s;   //离散化
	
	int tot=1;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];   //输入坐标
		mp[1ll*x[i]*P+y[i]]=tot;   //给点编号
		tot++;
		s[{x[i],y[i]}]=i;   //这个坐标是第几个城市
	}
	
	p.assign(tot+1,0);
	for(int i=1;i<=tot;i++){
		p[i]=i;
	}
	
	vector<int> c(n+1),k(n+1);
	
	for(int i=1;i<=n;i++){    //输入建立发电站需要的成本以及建树
		cin>>c[i];
		add(0,0,x[i],y[i],c[i]);
	}
	for(int i=1;i<=n;i++){   //输入拉线需要的成本
		cin>>k[i];
	}
	
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){   //遍历两个点
			int sx=x[i],sy=y[i];   //坐标
			int ex=x[j],ey=y[j];
			int d=abs(sx-ex)+abs(sy-ey);  //两个城市的距离 
			ll w=1ll*d*(k[i]+k[j]);   //每两个城市拉线的成本
			add(sx,sy,ex,ey,w);   //建树
		}
	}
	
	sort(v.begin(),v.end(),cmp);   //树里面排序
	ll ans=0;
	vector<pii> path;   //需要链接哪两个城市
	vector<int> city;    //在哪个城市建发电站
	for(int i=0;i<v.size();i++){
		int sx=v[i].sx,sy=v[i].sy,ex=v[i].ex,ey=v[i].ey,w=v[i].w;
		int a=mp[1ll*P*sx+sy],b=mp[1ll*P*ex+ey];  //编号
		a=find(a),b=find(b);   //判断是否在同一个树上
		if(a!=b){
			p[a]=b;   //合并集合
			ans+=w;   //费用等于两个点之间所需要花费的
			int x=s[{sx,sy}],y=s[{ex,ey}];
			if(sx==0&&sy==0){     //
				city.push_back(y);   //
			}
			else{
				path.push_back({x,y});
			}
		}
	}
	cout<<ans<<"\n";
	cout<<city.size()<<"\n";
	for(auto x:city){
		cout<<x<<' ';
	}
	cout<<"\n";
	cout<<path.size()<<"\n";
	for(auto x:path){
		cout<<x.first<<' '<<x.second<<"\n";
	}
	
	
	return 0;
}