poj2455 k条路最小化最长边
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 12414 | Accepted: 3625 |
Description
The farm comprises N (2 <= N <= 200) landmarks (numbered 1..N) connected by P (1 <= P <= 40,000) bidirectional trails (numbered 1..P) and with a positive length that does not exceed 1,000,000. Multiple trails might join a pair of landmarks.
To minimize his chances of detection, FJ knows he cannot use any trail on the farm more than once and that he should try to use the shortest trails.
Help FJ get from the barn (landmark 1) to the secret milking machine (landmark N) a total of T times. Find the minimum possible length of the longest single trail that he will have to use, subject to the constraint that he use no trail more than once. (Note well: The goal is to minimize the length of the longest trail, not the sum of the trail lengths.)
It is guaranteed that FJ can make all T trips without reusing a trail.
Input
* Lines 2..P+1: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, indicating that a trail connects landmark A_i to landmark B_i with length L_i.
Output
Sample Input
7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
Sample Output
5
二分最长边,然后按边的权值排序加边,然后加边权值是1,就可以保证一条路只能用一次了。然后判断最大流,如果大于等于路的数量,就说明true,然后二分就可以了
注意无向图加反向边的时候权值不是0
最新文章
- (jms)ActiveMQ 安装配置.
- Ubuntu 安装OpenERP
- 怎样在IDEA中使用JUnit4和JUnitGenerator V2.0自动生成测试模块
- 每天一点Android干货-Activity的生命周期
- LeetCode&mdash;&mdash;Same Tree(判断两棵树是否相同)
- HDOJ 1301
- 数列极限---和Gauss(取整)函数有关
- Hibernate criteria 混合sql语句多表关联时查询注意事项
- Java对数组对象进行排序
- python生成器之斐波切纳数列
- jQuery应用操作之---复选框
- man scp
- Centos6.5的MySQL5.7.15二进制源码单机版安装
- stm32+rx8025
- Webpack 常用命令总结以及常用打包压缩方法
- Android与js交互拍照上传资料
- android环境的搭配
- allegro 基本步骤
- 【Spark】SparkStreaming-提交到集群运行
- Django框架----Web框架本质
热门文章
- 走 进 java 的 四 个 基 本 特 性
- mysql不同端口的连接
- ES6中Fetch的封装及使用,炒鸡简单~
- IDC:企业需求疲软 第三季度全球服务器市场收入下滑7%
- 自动安装带nginx_upstream_check_module模块的Nginx脚本
- Nginx读书笔记三----资源分配
- 4)drf序列化组件 Serializer(偏底层)、ModelSerializer(重点)、ListModelSerializer(辅助群改)
- 记一次真实的线上事故:一个update引发的惨案!
- Java——Spring超详细总结
- Spring Cloud 学习 之 Spring Cloud Eureka(源码分析)