B - Shichikuji and Power Grid（ 最小生成树 Kruskal算法）

本文主要是介绍B - Shichikuji and Power Grid（ 最小生成树 Kruskal算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Shichikuji is the new resident deity of the South Black Snail Temple. Her first job is as follows:

There are nn new cities located in Prefecture X. Cities are numbered from 11 to nn. City ii is located xixi km North of the shrine and yiyi km East of the shrine. It is possible that (xi,yi)=(xj,yj)(xi,yi)=(xj,yj) even when i≠ji≠j.

Shichikuji must provide electricity to each city either by building a power station in that city, or by making a connection between that city and another one that already has electricity. So the City has electricity if it has a power station in it or it is connected to a City which has electricity by a direct connection or via a chain of connections.

• Building a power station in City ii will cost cici yen;
• Making a connection between City ii and City jj will cost ki+kjki+kj yen per km of wire used for the connection. However, wires can only go the cardinal directions (North, South, East, West). Wires can cross each other. Each wire must have both of its endpoints in some cities. If City ii and City jj are connected by a wire, the wire will go through any shortest path from City ii to City jj. Thus, the length of the wire if City ii and City jj are connected is |xi−xj|+|yi−yj||xi−xj|+|yi−yj| km.

Shichikuji wants to do this job spending as little money as possible, since according to her, there isn't really anything else in the world other than money. However, she died when she was only in fifth grade so she is not smart enough for this. And thus, the new resident deity asks for your help.

And so, you have to provide Shichikuji with the following information: minimum amount of yen needed to provide electricity to all cities, the cities in which power stations will be built, and the connections to be made.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

Input

First line of input contains a single integer nn (1≤n≤20001≤n≤2000) — the number of cities.

Then, nn lines follow. The ii-th line contains two space-separated integers xixi (1≤xi≤1061≤xi≤106) and yiyi (1≤yi≤1061≤yi≤106) — the coordinates of the ii-th city.

The next line contains nn space-separated integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1091≤ci≤109) — the cost of building a power station in the ii-th city.

The last line contains nn space-separated integers k1,k2,…,knk1,k2,…,kn (1≤ki≤1091≤ki≤109).

Output

In the first line print a single integer, denoting the minimum amount of yen needed.

Then, print an integer vv — the number of power stations to be built.

Next, print vv space-separated integers, denoting the indices of cities in which a power station will be built. Each number should be from 11 to nn and all numbers should be pairwise distinct. You can print the numbers in arbitrary order.

After that, print an integer ee — the number of connections to be made.

Finally, print ee pairs of integers aa and bb (1≤a,b≤n1≤a,b≤n, a≠ba≠b), denoting that a connection between City aa and City bb will be made. Each unordered pair of cities should be included at most once (for each (a,b)(a,b) there should be no more (a,b)(a,b) or (b,a)(b,a) pairs). You can print the pairs in arbitrary order.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

Examples

3
2 3
1 1
3 2
3 2 3
3 2 3

8
3
1 2 3 
0

3
2 1
1 2
3 3
23 2 23
3 2 3

27
1
2 
2
1 2
2 3

思路

1.我们建立源点，源点到每个点的距离设置为每个点建电站的权值，
2.这样做就可以将所有要求的值转化到图中来做了。
3.我们要求的就是一个最小生成树，算法魔板即可，然后把边输出完事了

代码：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int N=5000000 + 10;
//将图上点到点的信息存到s数组里
struct node{
   int u,v;
   ll w;
}s[N];

vector<int>e[N];
int f[N],a[N],b[N],k[N],vis[N];//f数组是, a,b数组是坐标 
int n,c,tot,cnt; //tot是s数组下标 cnt是建立电站的数量
ll ans;

void init(){
	ans=cnt=0;
	tot=1;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)
	f[i]=i;
}

int find(int x){
	if(x!=f[x])
        return f[x]=find(f[x]);
    else
        return x;
}

bool cmp(node a,node b){
	return a.w<b.w;
}

int main(){
	cin>>n;
	init();
	for(int i=1;i<=n;i++)
	cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++){
	  cin>>c;
	  s[tot].u=0;//这里就是新加了一个点0
	  s[tot].v=i; 
	  s[tot++].w=c;//核电站花费
    }
        for(int i=1;i<=n;i++)
	  scanf("%d",&k[i]);
  //计算各个城市间的连线花费 存到s数组
	for(int i=1;i<=n;i++){
	   for(int j=i+1;j<=n;j++){
	     s[tot].u=i;
	     s[tot].v=j;
	     s[tot++].w=(ll)(abs(a[i]-a[j])+abs(b[i]-b[j]))*(k[i]+k[j]);

	   }
        }
	sort(s+1,s+tot,cmp);
	for(int i=1;i<tot;i++){
		int fx=find(s[i].u);
		int fy=find(s[i].v);
		if(fx!=fy){
		   if(s[i].u==0){ //等于0的 w就是核电站花费
		     vis[s[i].v]=1;
	              cnt++; //核电站建立数
	           }
	           else
	           e[s[i].u].push_back(s[i].v);
	           ans+=s[i].w;//计算总花费
	           f[fy]=fx;
	        }
	}
	cout<<ans<<endl;
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++)
        if(vis[i])
        printf("%d ",i);
	cout<<endl;
	cout<<n-cnt<<endl;
	for(int i=1;i<=n;i++){
		for(int j=0;j<e[i].size();j++)
		printf("%d %d\n",i,e[i][j]);
	}
	return 0;
}

这篇关于B - Shichikuji and Power Grid（ 最小生成树 Kruskal算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！