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;

}

巴特西

codeforces 1245D（最小生成树）

最新文章

热门文章