Codeforces（D. Shichikuji and Power Grid）最小生成树+超级源点

原题链接：https://codeforces.ml/contest/1245/problem/D

最小生成树的作用之一？（转自知乎一个回答）：网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

贪心想了好长时间，都被否决了。

原来是要虚拟构建一个点，这个点到每个城市的权值为每座城市造发电厂的费用，而其他城市之间也都建立起链接，权值为两座城市铺设线路的费用。

这样跑一遍最小生成树就可以了，最后跑出来的结果就是最小花费。边跑边记录下哪些城市造发电站，哪些城市之间铺线。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct qq
{
    ll x,y;
}q[2005];;
struct node
{
    ll x,y;
    ll ans;
}edg[5000000];
ll c[2005],k[2005],f[2005];
bool cmp(node a,node b)
{
    if(a.ans<b.ans)
    {return 1;}
    return 0;
}
ll getf(ll u)
{
    if(f[u]==u)
    {return u;}
    else
    {
        f[u]=getf(f[u]);
        return f[u];
    }
}
void mange(ll u,ll v)
{
    ll t1=getf(u);
    ll t2=getf(v);
    if(t1!=t2)
    {f[t2]=t1;}
}
void init()
{for(int i=0;i<=2005;i++)
{f[i]=i;}}
 
ll book[2005],d[2005],id,ix;
struct xxxx
{
    ll x,y;
}x[2005];
int main()
{
    init();
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>q[i].x>>q[i].y;}
    for(int i=1;i<=n;i++)
    {cin>>c[i];}
    for(int i=1;i<=n;i++)
    {cin>>k[i];}
    ll cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j){continue;}
            edg[cnt].x=i;
            edg[cnt].y=j;
            edg[cnt].ans=(k[i]+k[j])*(abs(q[i].x-q[j].x)+abs(q[i].y-q[j].y));
            cnt++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        edg[cnt].x=0;
        edg[cnt].y=i;
        edg[cnt].ans=c[i];
        cnt++;
    }
    sort(edg,edg+cnt,cmp);
    ll ans=0;
    for(int i=0;i<cnt;i++)
    {
        if(getf(edg[i].x)!=getf(edg[i].y))
        {
            if(edg[i].x==0)
            {
                mange(edg[i].x,edg[i].y);
                ans+=edg[i].ans;
                d[id++]=edg[i].y;
            }
            else
            {
                mange(edg[i].x,edg[i].y);
                ans+=edg[i].ans;
                x[ix].x=edg[i].x;
                x[ix].y=edg[i].y;
                ix++;
            }
        }
    }
    cout<<ans<<endl;
    cout<<id<<endl;
    for(int i=0;i<id;i++)
    {cout<<d[i]<<" ";}
    cout<<endl;
    cout<<ix<<endl;
    for(int i=0;i<ix;i++)
    {cout<<x[i].x<<" "<<x[i].y<<endl;}
    return 0;
}

代码跑了近1000ms，但有个大佬的代码跑了77ms