计蒜客 Our Journey of Dalian Ends 费用流找最短路

Our Journey of Dalian Ends

题意

给一个无向图,有边权,每个点用地名字符串表示。现在要从大连出发到达西安,并且必须经过上海,且给个点只能经过一次,问最短路径。

建图&思路

  1. 可以认为是找两条路径,起点都是上海,分别到达西安和大连,且经过的点不能重复,求路径和的最小长度。
  2. 将每个点拆点,拆分为入点和出点,入点向出点连一条边,容量为$1$,费用为$0$,代表这个点只能经过一次。
  3. 对于原图上的点,从一个城市的出点连一条边,到另一个城市所代表的点的入点。容量为$1$,费用为这条边的边权。反过来也需要连一条边,代表双向可行。
  4. 从源点向上海的出点连一条边,容量为$2$,费用为$0$,代表需要找到两条路径。
  5. 从西安和大连的出点,分别引一条边到汇点,容量为$1$,费用为$0$,代表只能是以这两个点为终点。
  6. 跑费用流,如果流量为2,那么费用就是两条路径的最短长度。
  7. 当然,如果输入数据中没有这三个城市,直接不行啊!

代码

 

 

Codeforces 863F 费用流求最小花费方案

Codeforces 863F

题意

  • 构造一个长度为$n$的序列$a_i$($1 \leq n \leq 50, 1 \leq a_i \leq n$),需要满足$q$个条件($0 \leq q \leq 100$)
  • 对于每一个条件,有一下两种可能
    1 $l_i,r_i,v_i$,对于所有满足$l_i \leq x \leq r_i$的下标$x$,有$a_x \geq v_i$
    2 $l_i,r_i,v_i$,对于所有满足$l_i \leq x \leq r_i$的下标$x$,有$a_x \leq v_i$
  • 构造出该序列的花费$cost = \sum_{i=1}^{n}cnt(i)^2$,其中$cnt(i)$为数$i$在构造的序列中出现的次数,求最小的花费。

建图

  • 先确定每个位置能填的数的范围,如果范围非法,可直输出$-1$并结束
  • 左边$n$个点,分别代表$1~n$这$n$个位置上的数,从源点引一条边,到左边的每一个点,容量为$1$,费用为$0$。
  • 右边也有$n$个点,分别代表填写的数。对于每个点,向汇点引$n$条边,第$j$条边的容量为$1$,费用为$j^2-(j-1)^2$。
  • 对于左边的每个点,向范围内的数对应的右边的数连边,容量为$1$,费用为$0$。
  • 由于费用流会优先使用费用较小的边,所以对于一个单独的数对应的右边的点来说,他向汇点的边的,只会使用前几条,这几条边的费用加起来正好是通过这个点的流量的平方,满足题目要求。
  • 跑费用流,即可解决问题。

代码

 

CodeForces 818G 费用流 优化建图

CodeForces 818G

题意

给定一个长度为$n$的序列$a_i$,$4 \leq n \leq 3000,1 \leq a_i \leq 10^5$,从中选出$4$个不想交的子序列,满足每个子序列中相邻的两个项,要么是差的绝对值为$1$,要么他们模$7$的结果相同。问这四个序列的总长度最长为多少。


思路

  • 对于每个项来说,将其看成一个点,将其拆点为为$i$和$i+n$,从$i$向$i+n$引一条边,容量为$1$,费用为$-1$,表示该点项只能被选一次,且选了之后收益$+1$。这一对点的流量方向,一定为从$i$进,并且从$i+n$出。
  • 对于每个项来说,都有可能作为子序列的起点或者终点。所以,从源点引一条边到$i$点,容量为$1$,费用为$0$;再从$i+n$点引一条边到汇点,容量为$1$,费用为$0$。
  • 对于每一个可能相邻的项$a_i,a_j$且$i \lt j$来说,需要建一条边从$i+n$到$j$,容量为$1$,费用为$-1$。但是这样建边之后,会发现边很多,根本跑不过。其实会发现,对于每一类相邻来说,只需要往后找到四个是同类的并建边就好了。
  • 从源点压入$4$点流量,跑费用流即可,答案为最小费用的相反数。

代码

Codeforces 708D 费用流