Loj 6002 最小路径覆盖

题解:最小路径覆盖指在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。

最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1>3>4251->3->4,2,5

最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1>3>42>3>51->3->4,2->3->5

此题指的是最小不相交路径覆盖。

那么首先我们先考虑二分图上如何求出。 答案为nxn - xxx为最大匹配数。
感性理解:
假设当我们没有边的时候,此时的最小路径覆盖为nn 当我们不断加边,每加一条边进去,相当于最小路径覆盖1-1, 因为每个点只可被用一次。 那么很显然当最大匹配的时候 此时就是最小路径覆盖了

对于一个有向无环图。我们可以考虑他与二分图的区别。 二分图上任意一点时的匹配只能被使用一次。 而有向无环图上我们可以看到,对于某个点uu 可以被当作起点和终点各使用一次。 那么要如何处理这种情况。不妨试想拆点.将某点uu拆成u,uu, u' 表示起始点和终点。 那么假设uuvv有一条边。那么相当于将u>vu -> v' 连边。 那么我们可以发现这样可以恰好转成二分图的形式。跑一遍网络流即可。

输出方案: 暴力检查每条边残余网络是否为0,用并查集维护

Loj 6003 魔术球问题

题目:
假设有 nn 根柱子,现要按下述规则在这 $ n $ 根柱子中依次放入编号为 1,2,3,4,1, 2, 3, 4, \cdots 的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何 22 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 nn 根柱子上最多能放多少个球。

题解:考虑当i+ji + j为完全平方数的时候,那么ii可以向jj连边。假设我们已知现在要放xx个数,我们检验是否可行,是不是等价转换成求一个有向无环图上用最小路径? 那么我们只需要每次枚举并不断加边来判断此时是否满足nn个柱子即可

路径输出:参照上题暴力检查。

BZOJ 1066

考虑拆点,对一根柱子拆成起始点和终止点,连边权为柱的高度。超级源像所有蜥蜴连边权为1,所有终止点向超级汇连边权INF, 任意两个柱子距离d\leq d
连边权为INF
答案为蜥蜴总数减最大流

BZOJ 1877

费用流。拆点。对于每个除11nn的点之外拆点边权为11,任意两个点之间连边边权为11,费用为ww11nn拆点连边权为INF。跑一遍最小费用最大流即可

网络流24题 圆桌聚餐

最大流。建立超级源向每个代表团连边,边权为rir_i人数。 每个代表团向每个餐桌连边为1, 每个餐桌向超级汇点连边权为cic_i为容纳量。那么跑一遍最大流检验答案是否与代表团总人数相等即可。

方案输出:枚举每个代表团所在点的残余网络,如果存在边权为0输出即可。

网络流24题 最长上升子序列

最大流。第一问LIS dp即可。 第二问拆点,超级源S向每个f[i]=1f[i] = 1连边1,f[i]=maxlisf[i] = maxlis向超级汇T连边1. 每个点之间连边权为1。 第三问把1和n号点的边权改为 INF 即可。注意n==1n == 1的情况要特判

BZOJ 1834 网络扩容

第一问最大流为ans,第二问对于每一条边,我们新加一条同样的边加流量改为INF,费用改为扩容费用。 从nnn+1n+1连一条流量为ans+kans+k费用为0的边。从11n+1n+1跑一遍最小费用最大流即可