codeforces 1245D（最小生成树）_codeforces - 1245d

题面链接：https://codeforces.com/problemset/problem/1245/D

题意大概是给你一些城市的坐标，可以在城市中建立发电站，也可以让某个城市和已经建好发电站的城市连接，保证在这两种操作下使得所有的城市供电，在城市建发电站需要花费Ci，城市a和城市b连接需要花费（|Xa-Xb| + |Ya-Yb| ）*（Ka+Kb），求最小的花费让所有城市通电。

思路：首先建立一个源点，连接各个城市，边权就是建发电站费用Ci，若选择此边则表示是在该城市建了发电站。

           剩下的城市互相按照题意要求建边，建完全图。

           最终模型就抽象成求最小生成树，用克鲁斯卡尔算法跑一下即可

AC代码：

#include<iostream>
#include<vector>
#include<set>
#include<cstdio> 
#include<algorithm>
#define maxn 2005
using namespace std;
typedef long long ll;
struct node{
	int from,to;
	ll cost;
}e[maxn*maxn];//存储边的信息 
int father[maxn];
int cnt,N,city;
vector<int> sta;//存建发电站的城市 
vector<int> citya,cityb;//存储a b城市表示ab之间有电线 
bool cmp(node a,node b){//比较函数 
	return a.cost < b.cost ;
}
void init(){//初始化 
	cnt = 0;
	for(int i = 0;i<=N;i++){
		father[i] = i;
	}
}
int find(int x){//寻找根 
	if(x == father[x]) return x;
	return father[x] = find(father[x]);
}
bool same(int x,int y){//判断是否在一个集合 
	return find(x)==find(y);
}
void unionSet(int x,int y){ //并查集合并 
	int u = find(x),v = find(y);
	if(u==v) return ;
	father[u] = v;
}
long long kruskal(){ //求最小生成树 
	ll res = 0;
	std::sort(e,e+cnt,cmp);
	for(int i = 0;i<cnt;i++){
		if(same(e[i].from,e[i].to )) continue;
		unionSet(e[i].from ,e[i].to );
		if(e[i].from == 0 || e[i].to == 0){//判一下是否在城市建了发电站（利用源点判断） 
			if(e[i].from == 0) sta.push_back(e[i].to ); 
			else sta.push_back(e[i].from); 
		}
		else{//如果不是，存一些a,b两座连接的城市 
			citya.push_back(e[i].from ),cityb.push_back(e[i].to);  
		}
		res+=e[i].cost ;
	}
	return res; 
}
void addedge(int u,int v,ll C){ //建边操作 
	e[cnt].from = u,e[cnt].to = v,e[cnt].cost = C;
	cnt++;
}
int main(){
	cin>>N;
	init(); 
	vector<long long> vx,vy;
	vector<long long> c,k;
	for(int i = 0;i<N;i++){
		int x,y;cin>>x>>y;
		vx.push_back(x),vy.push_back(y);  
	}
	for(int i = 0;i<N;i++){
		ll tc;cin>>tc;
		c.push_back(tc); 
	}
	for(int i = 0;i<N;i++){
		ll tk;cin>>tk;
		k.push_back(tk); 
	}
	for(int i = 0;i<N;i++){//建立源点，和各个城市连接 
		addedge(0,i+1,c[i]);
	}
	for(int i = 0;i<N;i++){//城市和城市之间建完全图 
		for(int j = i+1;j<N;j++){
			ll c = (abs(vx[i]-vx[j])+abs(vy[i]-vy[j]))*(k[i]+k[j]);
			addedge(i+1,j+1,c);
		}
	}
	ll ans = kruskal();
	cout<<ans<<endl;
	cout<<sta.size()<<endl;
	for(int i = 0;i<sta.size();i++){
		if(i==0) cout<<sta[i];
		else cout<<" "<<sta[i];
	}
	cout<<endl;
	cout<<citya.size()<<endl;
	for(int i = 0;i<citya.size() ;i++){
		cout<<citya[i]<<" "<<cityb[i]<<endl;
	}
	return 0;
}