题目大意

要建设一个村庄的网络

有两种操作可选

1、给中国移动交宽带费,直接连网,花费为 A。
2、向另外一座有网的建筑,安装共享网线,花费为 B×两者曼哈顿距离。
 
题解
显然的最小生成树的题
见一个虚拟源点,将每个点和那个虚拟源点连一个边权为A的边
其余每个点之间连边,边权即为曼哈顿距离*B
于是自信的以为曼哈顿距离就是两点之间的距离的我,怎么都过不了大样例,于是快乐gg,快乐崩溃...
 
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std; inline int read()
{
int sum = ,p = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-')
p = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
(sum *= ) += ch - '';
ch = getchar();
}
return sum * p;
} const int N = 1e3 + ;
int n,A,B;
struct node
{
int x,y;
} pot[N];
int cnt,fa[N],tot;
struct edge
{
int frm,to;
ll wei;
} e[N * N / + N];
ll ans; void add(int a,int b,ll c)
{
e[++cnt].frm = a;
e[cnt].to = b;
e[cnt].wei = c;
} bool cmp(edge a,edge b)
{
return a.wei < b.wei;
} int findfa(int x)
{
if(fa[x] == x)
return x;
else
return fa[x] = findfa(fa[x]);
} void kruskal()
{
sort(e+,e+cnt+,cmp);
for(int i = ;i <= n;i++)
fa[i] = i;
for(int i = ;i <= cnt;i++)
{
int u = findfa(e[i].frm);
int v = findfa(e[i].to);
if(u == v)
continue;
fa[v] = u;
tot++;
ans += e[i].wei;
if(tot == n)
return;
}
} int main()
{
freopen("pupil.in","r",stdin);
freopen("pupil.out","w",stdout);
n = read(),A = read(),B = read();
for(int i = ; i <= n; i++)
{
pot[i].x = read();
pot[i].y = read();
}
for(int i = ; i <= n; i++)
for(int j = i + ; j <= n; j++)
{
ll xx= abs(pot[i].x - pot[j].x);
ll yy= abs(pot[i].y - pot[j].y);;
add(i,j,(xx + yy) * B);
// add(j,i,len * B);
}
for(int i = ;i <= n;i++)
{
add(,i,A);
// add(i,0,A);
}
kruskal();
printf("%lld\n",ans);
return ;
}
//不知道曼哈顿距离可还行

最新文章

  1. 『.NET Core CLI工具文档』(十三)dotnet-publish
  2. Android 更新UI的几种方式
  3. Bootstrap左侧下拉三级菜单
  4. 【原】flux学习笔记
  5. 【leetcode】Bitwise AND of Numbers Range(middle)
  6. silverlight 富文本
  7. Sensor信号输出YUV、RGB、RAW DATA、JPEG【转】
  8. linux包转发开发
  9. SRM 502 DIV1 500pt(DP)
  10. oc学习之路----多级指针的使用和内存分析
  11. Android开发学习之路--基于vitamio的视频播放器(二)
  12. 分析RunTime执行命令以及得到返回值
  13. spring中一些aware接口
  14. cucumber学习笔记
  15. Nginx 安装与部署配置以及Nginx和uWSGI开机自启
  16. SQL Server的实例恢复解析
  17. [Python] Print input and output in table
  18. 截取字符串substr和subString的却别
  19. 这些HTML、CSS知识点,面试和平时开发都需要 No5-No7(知识点:文字设置、设置背景、数据列表)
  20. requests+BeautifulSoup详解

热门文章

  1. The sklearn preprocessing
  2. 在vue项目中播放m3u8格式视频
  3. centos因为安装花生壳而无法登录系统的问题
  4. 使用pycharm搜索框和正则表达式匹配内容
  5. SQL语句中count(1)count(*)count(字段)用法的区别(转)
  6. cmd 运行py脚本,提示找不到xx模块
  7. 使用wsgiref手撸web框架
  8. axios的基本用法与并发请求
  9. hibernate跟Mybatis/ ibatis 的区别,为什么选择?(转)
  10. java简单学生成绩管理系统