网络流

[> 目录在这里 <]---------------------------------------------------------------------------------------------------------->

前置知识

最大流dinic模板
费用流EK模板

1.输出方案

  1.飞行员配对问题 [luogu P2756]

  简要题解:
  用最大流求最大匹配。源点向每一个外籍飞行员建容量为1的边,每一个英国飞行员向汇点建容量为1的边,两个可以匹配的飞行员之间连容量为1的边。

  设最大流为maxflow,则一定有maxflow条边流量为1(流满)。于是仅需要找出所有流满了的边输出起点和终点(注意判重否则会输出两遍)

上一篇:c#操作数据库导出Excel表


下一篇:P5331 [SNOI2019]通信 [线段树优化建图+最小费用最大流]