Luogu 2756 – 飞行员配对方案问题

题目链接:Luogu 2756 – 飞行员配对方案问题

二分图最大匹配,左边的点连到超级源,右边的点连到超级汇,所有边的容量为1,跑Dinic算法。

跑完后看edges数组里符合条件的为匹配边。主要考虑三点:

  • 这条边已经流满,即flow和cap相等
  • 这条边是正向边
  • 这条边连接的是二分图左边的点和右边的点,即两个端点不含s和t

 

说点什么

avatar
50
  Subscribe  
提醒