题目描述:点击进入
思路
最小生成树的变形
我们虚拟一个 “零” 结点,这个结点跟每个村庄 i 连边,权值分别为在村庄 i 建立一个网络中心的花费。然后其他边都正常连,最后求最小生成树即可。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
const int N=1e7+10;
int pre[maxn],n;
struct node
{
int x;
int y;
int c;
ll k;
}p[maxn];
struct Node
{
int x;
int y;
ll k;
}s[N];
int find(int x)
{
if(x==pre[x]) return x;
else return pre[x]=find(pre[x]);
}
bool unions(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fy]=fx;
return 0;
}
else return 1;
}
ll look(int i,int j)
{
ll dis=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
return dis*(p[i].k+p[j].k);
}
bool cmp(Node e,Node f)
{
return e.k<f.k;
}
int main()
{
while(~scanf("%d",&n))
{
int cnt=0;
for(int i=0;i<=n;i++) pre[i]=i;
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i].c);
s[++cnt].x=0;
s[cnt].y=i;
s[cnt].k=p[i].c;
}
for(int i=1;i<=n;i++) scanf("%d",&p[i].k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
s[++cnt].x=i;
s[cnt].y=j;
s[cnt].k=look(i,j);
}
}
sort(s+1,s+cnt+1,cmp);
ll ans=0;
for(int i=1;i<=cnt;i++)
{
if(!unions(s[i].x,s[i].y))
ans+=s[i].k;
}
printf("%lld\n",ans);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)