Phecda_

分类

未归档(109)

/ 注册

全部文章（共5篇）

LuoGu P1004 方格取数

题目传送门一开始这个题我是不会的(沙华弱DP啊QwQ)，后来考完试我一想，这东西怎么和数字三角形那题这么像啊？都是自上而下，只能向下或者向右，求一个max 那么...这不就是个走两遍的数字矩阵嘛转移方向都没换:对于(i,j)，只能由(i-1,j)或(i,j-1)转移过来转移解决了，那...

DP 网络流

2018-09-06

0 504

网络流小结

网络流小结联赛过后,虽然遗憾的没拿到一等,但这不是止步不前的时候,于是我就学了学网络流,学了这几天,也该总结总结了...... 网络流其实就是一种图论模型,在这种图中,边权变成了坑爹的流量,常见的最短路问题也变成了最大流-最小割问题网络图和普通图的最大区别也就是边权不再是一个***巴巴的数...

网络流

2019-03-31

0 291

二分图匹配

你以为我要讲匈牙利?不不不,我不会.我是要讲网络流哒! 呃,我直接说怎么搞吧你把二分图的两边节点搞出来,左边连一个超级源点,容量为 1 右边连一个超级汇点,容量为 1 然后跑从源到汇的最大流最大流就是最大匹配,至于为什么...这里借用一下大佬的证明: 首先假设，当前流网络有一个最大流，...

网络流二分图最大匹配

2019-04-28

0 375

飞行员配对方案问题

飞行员配对方案问题传送门读完题,就知道这就是个裸的二分图皮配,然后,我还是不说匈牙利,(因为我真的不会啊!) 所以,我还是用了喜闻乐见的 Dinic 并且跑的也不慢.唯一难点就是输出方案了吧...输出方案用最后的连通性判断,这题就没了.... Code: #include <io...

网络流二分图最大匹配

2019-04-28

0 306

CodeForces1214D

CodeForces1214D 这个题据我所知有两种比较优秀的做法. 第一种是\(DP\)统计每个点的路径数,然后找出必经点,再从必经点开始\(bfs\)堵路. 第二种比较简单,你先\(bfs\)一遍,如果不连通,直接输出\(0\),否则,找到任意一条路径(可以发现,一定是最短路)堵死. 然后重复这...

bfs 网络流 CodeForces

2019-09-05

0 424