首页 技术 正文
技术 2022年11月15日
0 收藏 900 点赞 2,928 浏览 492 个字

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3504

分析:很容易想到最大流,但如果S-a1,S-b1,a2-T,b2-T这样跑S-T最大流判断是否是满流的话,那么会出现an中间有一部分流从a1-b2,等量的流从b1-a2,这就不符合题意了,于是本渣弱弱翻了题解……

神犇的题解:先按上述跑一边最大流,再把b2当起点,b1当终点跑最大流,如果两次都满流,那么满足。

下面弱弱证明一下第二次最大流的正确性:

设:

a1->a2=an-x

a1->b2=x

b1->a2=x

b1->b2=bn-x

那么我们将b1,b2反过来后,则一定有

b2->b1=bn-x(没满,还可以流)

a1->a2=an-x(没满,还可以流)

可以看到最后都是差了x的流没有满流,但我们最后第二次是做出了满流,所以一定是还有a1->b1=x(a和b是等效的啦啦=+=)

那么a1既可以给b1流x,也可以给b2流x,又由于道路双向,那么可以把a1->b1的流量改为b2->a1->b1总共x的流量,那么b2->b1不就变成了bn了吗,同理a也是一样的,所以就撸完了……

Orz神题

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,082
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,556
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,406
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,179
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,815
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,898