CodeForces - 1245D（思维+最小生成树）

佚名 6年前 (2019-11-13) 算法 1895人围观抢沙发百度已收录

题意

https://vjudge.net/problem/CodeForces-1245D

已知一个平面上有 n 个城市，需要个 n 个城市均通上电

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

一个城市有电，必须在这个城市有发电站或者和一个有电的城市用电缆相连

在一个城市建造发电站的代价是 c[i]

i和 j 两个城市相连的代价是 k[i]+k[j] 乘上两者的曼哈顿距离

求最小代价的方案

输入:

第一行为城市个数

下面是每个城市的坐标

下面是建造发电站的代价 c[i]

下面是每个城市连线的系数 k[i]

输出:

一个为最小代价

建造发电站的城市数，和每个城市

连线的条数，和每条连线

任意一种即可，输出顺序任意

思路

将所有点两两之间连边，权值为k[i]+k[j] 乘上两者的曼哈顿距离，新建一个点0，其他点和0如果连边说明这个点建发电站。

跑一遍最小生成树即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=2005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
bool vis[N];
int lowc[N],n,pre[N];
ll prim(ll cost[][N])
{
    ll ans=0;
    memset(vis,false,sizeof(vis));
    vis[0]=true;
    for(int i=1; i<=n; i++)
    {
        lowc[i]=cost[0][i];
    }
    for(int i=1; i<=n; i++)
    {
        ll minc=1e16;
        int p=-1;
        for(int j=0; j<=n; j++)
        {
            if(!vis[j]&&minc>lowc[j])
            {
                minc=lowc[j];
                p=j;
            }
        }
        if(minc==inf)   return -1;
        ans+=minc;
        vis[p]=true;
        for(int j=0; j<=n; j++)
        {
            if(!vis[j]&&lowc[j]>cost[p][j])
                lowc[j]=cost[p][j],pre[j]=p;
        }
    }
    return ans;
}
struct node
{
    ll x,y,c,k;
} g[N];
ll G[N][N];
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>g[i].x>>g[i].y;
    }
    for(int i=1; i<=n; i++)
        cin>>g[i].c;
    for(int i=1; i<=n; i++)
        cin>>g[i].k;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            G[i][j]=G[j][i]=(g[i].k+g[j].k)*(abs(g[i].x-g[j].x)+abs(g[i].y-g[j].y));
        }
    }
    for(int i=1; i<=n; i++)
    {
        G[0][i]=G[i][0]=g[i].c;
    }
    cout<<prim(G)<<endl;
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(pre[i]==0)
            cnt++;
    }
    cout<<cnt<<endl;
    for(int i=1; i<=n; i++)
    {
        if(pre[i]==0)
        {
            cout<<i<<" ";
        }
    }
    cout<<endl;
    cnt=n+1-1-cnt;
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(pre[j]==i||pre[i]==j)
            {
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    return 0;
}