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$。
  • 由于费用流会优先使用费用较小的边,所以对于一个单独的数对应的右边的点来说,他向汇点的边的,只会使用前几条,这几条边的费用加起来正好是通过这个点的流量的平方,满足题目要求。
  • 跑费用流,即可解决问题。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注