文档章节

【ACM小思】有关一道费用流的思考

KningTG
 KningTG
发布于 2017/08/14 10:41
字数 394
阅读 5
收藏 0

魔改费用流一道

n个城市,p条双向道路把这些城市连接起来,一对城市之间可能有多条道路连接。FJ要找到t条从城市1到城市n的路径,不同的路径不能包含相同的道路。在这一前提条件下,FJ希望所有路径中经过的最长的道路最短。

​ 乍一看是一个网络流的问题

​ 路径不能重复,那就把边的容量当做1,最后求汇点流量为t的情况,增广的过程其实就是找路的过程。

但问题是怎么求出最短的最长边权?一种朴素的想法是二分答案,让所有边权超出要求的边断流,然后验证条件就是最大流是否大于t。

​ 已经是个不错的算法了。

​ 但是,我们还可以做得更好!

​ 还记得费用流是怎么做的吗?从源到汇不断找最短路,找到一次增广一次。而最短路的性质是“找出路径上所有边权的和”,但是我们这里想要的是保证这两个点之间的最大边权最短。

​ 最小生成树?

​ 对,实际上无论是最短路和最小生成树,都是求出“满足特定性质的路径”的一种方法。

​ 那我们不妨把最小费用流改一改?就像我们之前对最短路做的拓展思考一样。

​ 正解,就是如此。

© 著作权归作者所有

KningTG
粉丝 0
博文 2
码字总数 2146
作品 0
温州
私信 提问
网络流&二分图 12 - 05

二分图匹配 有向图的最小路径覆盖 把每个点拆成两个点,一个负责进边,一个负责出边,最小路径覆盖 二分图的最小点覆盖 二分图的最大独立点集 春天来了 Description 这里有 每个人都有一个腼...

aziint
2017/12/17
0
0
郑州大学2018新生训赛第十场题解

  比赛(补题)地址:http://222.22.65.164/contest.php?cid=1013   总述:这次新生赛难度偏于平和,但涵盖方面甚广,其中一道签到题是c语言题,并且有两道是hdu一百题的原题,一道简单的...

moonfair
2018/11/17
0
0
C中括号优先级的思考

问题源于论坛的一道题目: http://topic.csdn.net/u/20100216/21/ec98464e-a47e-4263-bb1c-a001e130ba87.html 下面是问题: 问题的焦点也落在printf执行的问题上,到底先执行谁,后执行谁, ...

晨曦之光
2012/03/09
134
0
关于一道数学建模问题,有关模拟退火,急求解!!!

A题: 供应链网络的建立与道路破坏问题 *****(只求如何通过模拟退火找出合适的供应点) ***** 全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略,以实现企业的一体化管理。供应链是...

Eta1
2013/04/29
782
1
IT连创业系列:创业者逆境下的思维

  距上篇文章,又半个多月过去了,是时候来一发阶段性的总结了。   可能最近比较懒,也可能是想不到写文的主题,故写文已变成越来越艰难的一个任务。   这个系列的大标题,也改了:它从...

路过秋天
2017/09/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
6
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
8
0
详解箭头函数和普通函数的区别以及箭头函数的注意事项、不适用场景

箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程度还是不够深... 普通函数和...

OBKoro1
昨天
7
0
轻量级 HTTP(s) 代理 TinyProxy

CentOS 下安装 TinyProxy yum install -y tinyproxy 启动、停止、重启 # 启动service tinyproxy start# 停止service tinyproxy stop# 重启service tinyproxy restart 相关配置 默认...

Anoyi
昨天
2
0
Linux创建yum仓库

第一步、搞定自己的光盘 #创建文件夹 mkdir -p /media/cdrom #挂载光盘 mount /dev/cdrom /media/cdrom #编辑配置文件使其永久生效 vim /etc/fstab 第二步,编辑yun源 vim /ect yum.repos.d...

究极小怪兽zzz
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部