网络流 24 题

· · 个人记录

咕着呢，网络流早忘干净了

网络流24题

我那么菜，能写几道算几道吧……

1.P2756 飞行员配对方案问题

两两配对，求最多能有几对，没有边权。一眼顶针，裸的二分图最大匹配，只不过要求输出配对方案。

之前写的是匈牙利算法，但既然是网络流24题还是写一遍 Dinic。

CODE

22-11-20 20:32:58

2.P2763 试题库问题

显然的，从 S 到每个试题类型连一条边权为 a_i 的边，从每个试题类型到可以属于这个类型的所有点连一条边权为 1 的边，从每道题到 T 连一条边权为 1 的边，只有最大流等于 m 时才有解。

CODE

22-11-20 21:30:31

3.P2764 最小路径覆盖问题

最小路径覆盖模型模板题。

网络流跑的没匈牙利快。

CODE

22-11-21 08:41:58

4.P2765 魔术球问题

之前写过匈牙利，不想再写网络流了，网络流又臭又长（恼）。

最小路径覆盖模型变式题,不断尝试放上多少个球后可不可以，不可以就跳出。每次直接处理新加入的球与前面的球可不可以配对，暴力跑匈牙利。

CODE

22-10-09 16:55:30

5.P2770 航空路线问题

每个点只能经过一次，所以先考虑拆点。尽管有点像是最小路径覆盖问题，但要求求出的是一整条路径，并非若干条，所以不同于最小路径覆盖问题。

原图中边是双向边，从 1\to n\to 1 等同于找出没有重复经过的点的两条从 1\to n 的路径。额外要求尽可能经过更多的城市，所以要加入费用。

拆点后从 S\to 1 连一条边，从 n'\to T 连一条边，容量都为 2 ，因为在这个问题里只有这两个点可以经过两次，所以先不考虑从 S'\to S 和 T'\to T ，所以要直接这样连边。原图中每条边从西往东连边，容量为 1 即可。其他的从 i'\to i 连一条边，容量显然为 1 ，而这里代表到达了一个城市，所以费用为 1 （其他边费用都为 0 ）。

跑一边最大费用最大流即可，最后经过的点数要加 2 。

特殊情况是最大流小于 2 要输出 No Solution!，可能出现直接从 1\to n\to 1 的边，特判一下 1\to n 的边建两次/容量改为 2 即可。

CODE

22-11-22 10:21:11