[思维][虚点]Codeforces Round #597 (Div. 2) D. Shichikuji and Power Grid

题意：给定n个城市，求最小的权值使得所有城市都有电，对于每个城市要么建电站，要么连接到已经有电的城市，ij两点连接边权为(abs(arr[i].x - arr[j].x) + abs(arr[i].y - arr[j].y) ) * (arr[i].k + arr[j].k)，建电站权值为arr[i].c

解题思路：转换问题，把建电站也变为权值边，建电站代表连接虚点0的边，然后跑最小生成树即可。

对于答案，若抛开虚点后可能是一片森林，对每个森林跑生成树不好操作，而建虚点后权值统一操作统一

正确性：建虚点后跑最小生成树必然有至少一个电站，因为要将0点连接到树中，符合题意

最优，按边权排序后若出现了虚点边则表示在当前点建电站比权值更大的连接更优，最后按边类型统计即可

/*
    Zeolim - An AC a day keeps the bug away
*/
 
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
#define pb(x) push_back(x)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
const ull P = 13331; 
const int MAXN = 4e6 + 100;

int n;

struct pit
{
	ll x, y;
	ll k, c;
}arr[MAXN];

struct node
{
	ll x, y, val;
	bool operator < (const node b) const 
	{
		return val < b.val;
	}
}edge[MAXN];

int p = 0;

int fa[MAXN] = {0};

int findfa(int x)
{
	return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}

int main()
{  
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("d:out.txt","w",stdout);
    //freopen("d:in.txt","r",stdin);
   	
    cin >> n;
    
    
    for(int i = 0; i < n + 10; ++i) fa[i] = i;
    
    for(int i = 1; i <= n; ++i)
    	cin >> arr[i].x >> arr[i].y;
    	
    for(int i = 1; i <= n; ++i)
    	cin >> arr[i].c;
    
    for(int i = 1; i <= n; ++i)
    	cin >> arr[i].k;
    
    for(int i = 1; i <= n; ++i)
    {
    	for(int j = i + 1; j <= n; ++j)
    	{
    		edge[p++] = node{i, j, (abs(arr[i].x - arr[j].x) + abs(arr[i].y - arr[j].y) ) * (arr[i].k + arr[j].k)};
		}
	}
    
    for(int i = 1; i <= n; ++i)
    {
    	edge[p++] = node{i, 0, arr[i].c};
	}
	
	sort(edge, edge + p);
	
	ll ans = 0;
	
	vector <int> bu;
	vector <pii> ad;
	
	for(int i = 0; i < p; ++i)
	{
		int p = findfa( edge[i].x ), q = findfa( edge[i].y );
		
		if(p != q)
		{
			fa[p] = q;
			ans += edge[i].val;
			
			if(edge[i].y == 0)
			{
				bu.pb(edge[i].x);
			}
			else
			{
				ad.pb(mp(edge[i].x, edge[i].y) );
			}
		}
	}
	
	
	cout << ans << '
';
	
	cout << bu.size() << '
';
	
	for(auto x : bu)
	{
		cout << x << ' ';
	}
	cout << '
';
	cout << ad.size() << '
';
	for(auto x : ad)
	{
		cout << x.first << ' ' << x.second << '
';
	}
	
	return 0;
}


/*
13 8
100 90 80 70 60 50 40 30
0
0
0
0
1
1
2
2
3
7
7
8
8
*/

/*
5 3
5 4 3
0
0
1
1
*/