Codeforces Round #597 (Div. 2)D. Shichikuji and Power Grid 神奇的最小生成森林

传送门
题意：n个城市，每一个城市有对应的Ci，Ki，和所在位置xi，yi；
Ci代表点亮这座城市的代价，
使两座城市连接起来的代价为（Ki+Kj）*曼哈顿距离；
问使所有城市都亮起来的最小代价

思路：非常容易想到，最终的结果一定是有几个城市被点亮，之后每个城市都会有他的附属城市（直接相连或间接相连）。
仔细想想，这不就是变成了几个树吗！！！
然后我们直接建立一个超级源点N+1（已经被点亮） 将他和所有的点连接起来，边权为Ci，在N^2处理出来所有连接两点的代价，当作边权。
然后直接求这个图的最小生成树就OK了！！！（每个连接N+1的城市即为直接被点亮的城市）
总结：
超级源点勉强算是本题难想的一个地方，之后就非常简单了啊！！真是不知道昨晚在干什么………………

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,v,e,x[2010],y[2010],c[2010],k[2010],fa[2010],rt[2010];
ll s;
struct T
{
    int x,y;
    ll z;
} a[4000001];
bool operator< (T a,T b)
{
    return a.z<b.z;
}
int fnd(int x)
{
    return x==fa[x]?x:fa[x]=fnd(fa[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)scanf("%d%d",&x[i],&y[i]);
    for(int i=1; i<=n; ++i)scanf("%d",&c[i]);
    for(int i=1; i<=n; ++i)scanf("%d",&k[i]);
    for(int i=1; i<n; ++i)
        for(int j=i+1; j<=n; ++j)
            a[++m]=T{i,j,1LL*(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]))};
    for(int i=1; i<=n; ++i)a[++m]=T{i,n+1,c[i]};
    sort(a+1,a+m+1);
    for(int i=1; i<=n+1; ++i)fa[i]=i;
    for(int i=1; i<=m; ++i)
    {
        int X=fnd(a[i].x),Y=fnd(a[i].y);
        if(X==Y)continue;
        if(a[i].x>n||a[i].y>n)rt[++v]=min(a[i].x,a[i].y);
        else ++e,x[e]=a[i].x,y[e]=a[i].y;
        s+=a[i].z;
        fa[X]=Y;
    }
    cout<<s<<endl<<v<<endl;
    for(int i=1; i<=v; ++i)cout<<rt[i]<<' ';
    cout<<endl<<e<<endl;
    for(int i=1; i<=e; ++i)cout<<x[i]<<' '<<y[i]<<endl;
}