Shichikuji and Power Grid

参考：Codeforces Round #597 (Div. 2)

思路：一个很裸的最小生成树。把建立基站看成是，城市与源点（虚构的）建边。由此建立最小生成树，即可得出答案。

代码：

// Created by CAD on 2019/11/2.

#include <bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

using namespace std;

const int maxn=2020*2000;

struct edge{

    ll u,v;

    ll w;

    bool operator<(edge &e)

    {

        return w<e.w;

    }

}e[maxn];

ll fa[2005],x[2005],y[2005],c[2005],k[2005];

int n;

vector<int> out1;

vector<pii> out2;

int find(int i)

{

    return i==fa[i]?i:fa[i]=find(fa[i]);

}

int cnt=0;

int cnt1=0;

ll kruskal()

{

    ll ans=0;

    for(int i=0;i<=n;++i)

        fa[i]=i;

    for(int i=1;i<=cnt;++i)

    {

        int u=find(e[i].u),v=find(e[i].v);

        if(u!=v)

        {

            ans+=e[i].w,fa[v]=u;

            if(!e[i].u) out1.push_back(e[i].v);

            else out2.push_back({e[i].u,e[i].v});

        }

    }

    return ans;

}

int main()

{

//    FOPEN;

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>n;

    for(int i=1;i<=n;++i)

        cin>>x[i]>>y[i];

    for(int i=1;i<=n;++i)

        cin>>c[i];

    for(int i=1;i<=n;++i)

        cin>>k[i];

    for(int i=1;i<=n;++i)

        e[++cnt]=edge{0,i,c[i]};

    for(int i=1;i<=n;++i)

        for(int j=i+1;j<=n;++j)

            e[++cnt]=edge{i,j,1ll*(abs(x[i]-x[j])+abs(y[i]-y[j]))*(k[i]+k[j])};

    sort(e+1,e+cnt+1);

    cout<<kruskal()<<endl;

    cnt1=out1.size();

    cout<<cnt1<<endl;

    for(int i=0;i<cnt1-1;++i)

        cout<<out1[i]<<" ";

    if(cnt1)

    cout<<out1[cnt1-1]<<endl;

    cout<<out2.size()<<endl;

    for(auto i:out2)

        cout<<i.first<<" "<<i.second<<endl;

    return 0;

}

巴特西

Shichikuji and Power Grid

最新文章

热门文章