題意
https://vjudge.net/problem/CodeForces-1245D
已知一個平面上有 n 個城市，需要個 n 個城市均通上電
一個城市有電，必須在這個城市有發電站或者和一個有電的城市用電纜相連
在一個城市建造發電站的代價是 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/125559.html
標籤：其他