Save your cats

题意:存在n个点,有m条边( input中读入的是 边的端点,要先转化为边的长度 ),做一个最小生成树,使得要去除的边的长度总和最小;

思路:利用并查集和求最小生成树的方法,注意这里的排序要从大到小排,这样最后建树的消耗最大,反过来去除的最小;

当然题意不是这么直白,感觉以后看到要做一个不成环的图时,要想到最小生成树;

下面是ac代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
const int maxn =;
const int mx =2e6+;
using namespace std;
int n,m,fa[maxn];
struct node {
int from;
int to;
double r;
}a[mx];
struct nn{
int x,y;
}p[maxn]; bool cmp(node a,node b)
{
return a.r>b.r; //这里的判断用大于,使得sort从大到小排列
}
void init(){
for(int i=;i<=n;i++)
fa[i] = i;
memset(a,,sizeof(a));
memset(p,,sizeof(p));
}
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x] = find (fa[x]);
}
bool uni(int x,int y)
{
int px = find(x);
int py = find (y);
if(px==py)return false;
fa[px] = py;
return true;
}
int main(){
scanf("%d%d",&n,&m);
init();
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
p[i].x=x;
p[i].y=y;
}
double sum = ,res=;
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
double tmp = sqrt((p[u].x-p[v].x)*(p[u].x-p[v].x)+(p[u].y-p[v].y)*(p[u].y-p[v].y));
a[i].from=u;
a[i].to=v;
a[i].r = tmp;
sum+=tmp;
}
sort(a+,a++m,cmp);
for(int i=;i<=m;i++)
{
int u = a[i].from;
int v = a[i].to;
if(uni(u,v))res+=a[i].r;
}
printf("%.3lf\n",sum-res);
return ;
}

最新文章

  1. awk 的使用
  2. memcached 常用命令及使用说明
  3. android相机调用及存储详解
  4. 20160130.CCPP体系详解(0009天)
  5. uploadify 上传
  6. Qt 自定义model实现文件系统的文件名排序
  7. hadoop错误java.io.IOException Failed to replace a bad datanode on the existing pipeline due to no more good datanodes being available to try
  8. java 百分比显示
  9. MyBatis_延迟加载01
  10. 线性回归中常见的一些统计学术语(RSE RSS TSS ESS MSE RMSE R2 Pearson&#39;s r)
  11. 写一个小CTF平台
  12. python推导式创建序列
  13. getchar(),scanf(),gets(),cin,输入字符串
  14. Codeforces Round #355 (Div. 2) D. Vanya and Treasure
  15. DCL,即Double Check Lock,中卫双重检查锁定。
  16. luoguP4491 [HAOI2018]染色 广义容斥原理 + FFT
  17. WPF 组织机构下拉树多选,递归绑定方式现实
  18. LeetCode——Find Duplicate Subtrees
  19. CSS样式编写案例
  20. 5.4WEB服务器、应用程序服务器、HTTP服务器区别

热门文章

  1. 【iOS】设备系统版本
  2. 对ThreadLocal的一些理解
  3. MyBatis 核心配置综述之StatementHandler
  4. Extjs的文件上传问题
  5. Python基础总结之认识lambda函数、map函数、filter() 函数。第十二天开始(新手可相互督促)
  6. 深入理解JVM-java字节码文件结构剖析(1)
  7. java多线程中wait/notify/sleep/join/yield方法以及多线程的六种状态
  8. golang 结合实例更好的理解参数传递和指针
  9. MySQL-EXPLAIN执行计划Extra解释
  10. Jmeter使用csv文件读取测试数据