bzoj 1189
2024-09-21 10:07:38
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1189
这道题目看起来好像要用很高端的网络流。
这道题有一个特别之处，就是每一个空地都有人，不是某些空地有人。
先二分时间mid,从源点S向空地连一条容量为1的边，空地向在时间mid内能到达的门连一条容量1的边，最后门向汇点T连一条容量为mid的边。
这样为什么是对的呢，能保证单位时间内只有一个人通过某个门吗？
我们来简单认识一下：
我们求到的最大流已经是满流了。
这时候有两个人a和b都去了门1，并且a和b去这个门的时间是一样的。
这好像是违反规定的。
但我们可以在a到门1的路上找一个人c，因为是满流，所以人c一定会有一个去处门2
我们可以换一下a去门2，c出门1，这样结果还是不变的。
这个说法好像比较粗略。。。。。。
最新文章
- [LeetCode] Maximal Rectangle 最大矩形
- MySql连接数据库和操作(java)
- Android学习笔记
- Gradle用户指南(2)-基本命令
- 关于equals和hashCode
- ios 中怎么自定义(RGB)背景色
- 慕课linux学习笔记（一）centOS的安装
- U10vim程序编辑器
- poj3176--Cow Bowling(dp:数塔问题)
- 编写简单的hashCode方法
- CentOS6.6 部署Apache+Svn
- maridb安装审计audit插件
- .NET Core微服务实施之Consul服务发现与治理
- [转]IIS应用程序池经典模式转集成模式解决方案
- bzoj4571/luogu3293 美味 (主席树+贪心)
- Hyperledger Fabric网络节点架构
- NSString json 车NSDictionary
- Java：多线程，线程同步，synchronized关键字的用法（同步代码块、非静态同步方法、静态同步方法）
- ASP.NET中登录功能的简单逻辑设计
- 完整的JavaScript版的信用卡校验代码