Phecda_

分类

未归档(109)

/ 注册

全部文章（共2篇）

二分图匹配

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

网络流二分图最大匹配

2019-04-28

0 375

飞行员配对方案问题

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

网络流二分图最大匹配

2019-04-28

0 306