传送门
题意:n个城市,每一个城市有对应的Ci,Ki,和所在位置xi,yi;
Ci代表点亮这座城市的代价,
使两座城市连接起来的代价为(Ki+Kj)*曼哈顿距离;
问使所有城市都亮起来的最小代价
思路:非常容易想到,最终的结果一定是有几个城市被点亮,之后每个城市都会有他的附属城市(直接相连或间接相连)。
仔细想想,这不就是变成了几个树吗!!!
然后我们直接建立一个超级源点N+1(已经被点亮) 将他和所有的点连接起来,边权为Ci,在N^2处理出来所有连接两点的代价,当作边权。
然后直接求这个图的最小生成树就OK了!!!(每个连接N+1的城市即为直接被点亮的城市)
总结:
超级源点勉强算是本题难想的一个地方,之后就非常简单了啊!!真是不知道昨晚在干什么………………
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,v,e,x[2010],y[2010],c[2010],k[2010],fa[2010],rt[2010];
ll s;
struct T
{
int x,y;
ll z;
} a[4000001];
bool operator< (T a,T b)
{
return a.z<b.z;
}
int fnd(int x)
{
return x==fa[x]?x:fa[x]=fnd(fa[x]);
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)scanf("%d%d",&x[i],&y[i]);
for(int i=1; i<=n; ++i)scanf("%d",&c[i]);
for(int i=1; i<=n; ++i)scanf("%d",&k[i]);
for(int i=1; i<n; ++i)
for(int j=i+1; j<=n; ++j)
a[++m]=T{i,j,1LL*(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]))};
for(int i=1; i<=n; ++i)a[++m]=T{i,n+1,c[i]};
sort(a+1,a+m+1);
for(int i=1; i<=n+1; ++i)fa[i]=i;
for(int i=1; i<=m; ++i)
{
int X=fnd(a[i].x),Y=fnd(a[i].y);
if(X==Y)continue;
if(a[i].x>n||a[i].y>n)rt[++v]=min(a[i].x,a[i].y);
else ++e,x[e]=a[i].x,y[e]=a[i].y;
s+=a[i].z;
fa[X]=Y;
}
cout<<s<<endl<<v<<endl;
for(int i=1; i<=v; ++i)cout<<rt[i]<<' ';
cout<<endl<<e<<endl;
for(int i=1; i<=e; ++i)cout<<x[i]<<' '<<y[i]<<endl;
}