POJ 2377 (并查集+sort求最远路)
Description
Realizing Farmer John will not pay her, Bessie decides to do the worst job possible. She must decide on a set of connections to install so that (i) the total cost of these connections is as large as possible, (ii) all the barns are connected together (so that it is possible to reach any barn from any other barn via a path of installed connections), and (iii) so that there are no cycles among the connections (which Farmer John would easily be able to detect). Conditions (ii) and (iii) ensure that the final set of connections will look like a "tree".
Input
* Lines 2..M+1: Each line contains three space-separated integers A, B, and C that describe a connection route between barns A and B of cost C.
Output
Sample Input
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
Sample Output
42
Hint
OUTPUT DETAILS:
The most expensive tree has cost 17 + 8 + 10 + 7 = 42. It uses the following connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.
#include<cstdio>
#include<algorithm>
using namespace std;
int sum,n,m,i,fa[];
int find(int a)
{
int r=a;
while(r != fa[r])
{
r=fa[r];
}
return r;
}
struct stu
{
int a,b,c;
}st[];
bool cmp(stu a,stu b)
{
return a.c>b.c;
}
void f1(int x,int y)
{
int nx,ny;
nx=find(x);
ny=find(y);
if(nx != ny)
{
fa[nx]=ny;
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
sum=;
for(i = ; i <= n ;i++)
{
fa[i]=i;
}
for(i = ; i < m ; i++)
{
scanf("%d %d %d",&st[i].a,&st[i].b,&st[i].c);
}
sort(st,st+m,cmp); //对最远路径排序
for(i = ; i < m ; i++)
{
if(find(st[i].a) != find(st[i].b)) //判断有没有环
{
f1(st[i].a,st[i].b);
sum+=st[i].c;
}
}
int ans=;
for(i = ; i <= n ; i++)
{
if(fa[i] == i) //判断有没有独立点
{
ans++;
}
}
if(ans > )
printf("-1\n");
else
printf("%d\n",sum);
}
}
最新文章
- Java中从控制台输入数据的几种常用方法
- easyui datagrid 点击表头的事件
- 2.5 ListView
- 学习总结(annotation)
- 虚拟机备份转移后,网络启动异常,提示“SIOCSIFADDR: No such device”的解决方案
- Oracle的AUTOTRACE功能
- Java多线程初学者指南(5):join方法的使用
- Behavioral模式之Observer模式
- 配置Windows Server 2012服务器远程连接支持多人同时登陆
- 10分钟学会JAVA注解(annotation)
- [poj3349]Snowflake Snow Snowflakes_hash
- 13-TypeScript单例模式
- Linux:Day8(下) RAID
- Java多线程-详细版
- 【Java】 剑指offer(45) 把数组排成最小的数
- 2017第八届蓝桥杯C/C++ B组省赛-购物单
- Netty Tutorial Part 1: Introduction to Netty [z]
- centos 删除文件和目录
- WeakValue &; StoreValue
- [Erlang33]使用recon从网页查看Erlang运行状态
热门文章
- 使用pytesseract识别验证码,报错WindowsError: [Error 2]
- Hdu 5445 Food Problem (2015长春网络赛 ACM/ICPC Asia Regional Changchun Online)
- HDU 4366 Successor 分块做法
- 如何正确从他人机器MySQL数据库下拷贝出.sql,再导入到自己windows下MySQL数据库(图文详解)
- JavaScript中函数是不能重载原因
- 【C#】枚举
- oracle 触发器,序列,索引
- 01认识Python和基础知识
- 在idea启动tomcat出现The JAVA_HOME environment variable is not defined correctly的解决
- xcode6的项目中虚拟键盘无法弹出