传送门

经典的最小生成树模型

建一个点 $0$ ,向所有其他点 $x$ 连一条边权为 $c[x]$ 的边,其他任意两点之间连边,边权为 $(k_i+k_j)(\left | x_i-x_j\right |+\left | y_i-y_j\right |)$

然后用 $prim$ 求个最小生成树即可,然后考虑一下输出方案

多维护一个 $frm[x]$ 表示当前的 $dis[x]$ 是从哪个点贡献来的就行了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=;
const ll INF=1e18;
int n,x[N],y[N],c[N],k[N];
inline ll cst(int i,int j) { return 1ll*(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j])); }
ll dis[N],ans;
bool vis[N];
vector <int> bas;
vector <pair<int,int>> edg;
int frm[N];
void Prim()
{
for(int i=;i<=n;i++) dis[i]=c[i];
for(int I=;I<=n;I++)
{
ll mx=INF; int pos=-;
for(int i=;i<=n;i++)
if(!vis[i]&&dis[i]<mx)
mx=dis[i],pos=i;
vis[pos]=; ans+=mx;
if(!frm[pos]) bas.push_back(pos);
else edg.push_back(make_pair(frm[pos],pos));
for(int i=;i<=n;i++)
if(!vis[i]&&dis[i]>cst(pos,i))
dis[i]=cst(pos,i),frm[i]=pos;
}
}
int main()
{
n=read();
for(int i=;i<=n;i++)
x[i]=read(),y[i]=read();
for(int i=;i<=n;i++) c[i]=read();
for(int i=;i<=n;i++) k[i]=read();
Prim(); printf("%lld\n",ans);
printf("%d\n",int(bas.size()));
for(auto x: bas) printf("%d ",x); puts("");
printf("%d\n",int(edg.size()));
for(auto t: edg) printf("%d %d\n",t.first,t.second);
return ;
}

最新文章

  1. mvc实现上传图片(上传和预览)webuploader
  2. FFT质数打表程序
  3. IE11下Forms身份认证无法保存Cookie的问题
  4. [linux]scp指令
  5. java作业3
  6. 两款HTTP流量分析工具HttpWatch与Fiddler的比较(转)
  7. ASPxCallback控件
  8. ylbtech-数据库设计与优化-对作为复选框/单选列表的集合表的设计
  9. MVVM模式应用 之xml文件的读取
  10. Sql Server 时间格式
  11. C语言 格式说明符
  12. printk
  13. DataReader的用法程序简析
  14. php文件的管理
  15. 改变图像,运用match方法判断
  16. Odoo之Field
  17. volatile 与 synchronized 区别
  18. Python面向对象——内置对象的功能扩展
  19. JAXB(Java Architecture for XML Binding)
  20. 使用IntelliJ IDEA和Maven管理搭建Web开发环境(以Spring MVC为例)(二)

热门文章

  1. BaggingClassifier
  2. Get Argument Values From Linq Expression
  3. GCC编译流程及常用编辑命令
  4. SQL-W3School-函数:SQL MIX() 函数
  5. VGG网络-ILSVRC-2014亚军
  6. HTML5 地理位置定位API(5)
  7. Eclipse中把项目导出为war包【我】
  8. 阶段5 3.微服务项目【学成在线】_day17 用户认证 Zuul_03-用户认证-认证服务查询数据库-查询用户接口-接口定义
  9. (十二)Centos之关机和重启
  10. git命令手册