计蒜客 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 546E Soldier and Traveling 最大流找可行方案

Codeforces 546E

题意

一个国家有$n$个城市,由$m$条双向边连接。现在,每个城市有$a_i$个士兵。现在每个士兵可以沿着一条边,走到相邻的城市,并且只能走一次,或者不走,留在原来的城市。问能否达到每个城市分别有$b_i$的士兵。切每条道路有一个上限,通过的士兵的个数不能超过这个上限。

  • 如果可以,输出"YES"。并输出方案,用矩阵$A_{ij}$表示从$i$城市走到$j$城市的士兵的个数。
  • 如果不可以,输出"NO"。

建图&思路

  1. 左边$n$个点,从源点往分别这$n$个点引一条边,容量为$a_i$。
  2. 右边$n$个点,从这个$n$个点分别往汇点引一条边,容量为$b_i$。
  3. 对于每一个城市$i$来说,从左边的第$i$个点向右边的第$i$个点引一条边,容量为$INF$,表示允许驻留。
  4. 对于每一条路来说,它的两个断点分别为$st,en$,那么需要从左边的第$st$个点引一条边到右边的第$en$个点,容量为这条路的上限。同时,从左边的第$en$个点引一条边到右边的第$st$个点,容量为这条路的上限。表示这两个城市之间的士兵可以相互移动,数量的上限不超过路的上限。
  5. 跑最大流,得到最大流量为$flow$,如果$flow$和士兵的总数相同,那么就有可行方案。否则没有。
  6. 对于每一个左边的点,枚举每一条向右边连的边,那么从这个点对应的城市到所连的点的城市所移动的士兵的个数,就是这条边所流过的流量,即这条边反向边的残余流量。

代码

注释

这个代码是2015年写的isap模板,所以不怎么好看。

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$点流量,跑费用流即可,答案为最小费用的相反数。

代码

2014-2015 ACM-ICPC Southwestern Europe Regional Contest (SWERC 14)

https://odzkskevi.qnssl.com/727b6827e404fd453ff4858e2619c49c?v=1504751451

A - GREAT+SWERC=PORTO

全排列枚举。先将字母按照出现的顺序,重新编码为以$0$为开始值的数字,方便后续使用。然后构造一个排列数组$p$,长度为$10$,初始值$p[i] = i$。然后枚举$p$的全排列,$p[i]$的意义就是将数字(实质上是被重新编码后的字母)$i$以值$p[i]$来代替。假设有$cnt$个不同的字母,全排列我们枚举的却是$10$个数,每次只取前$cnt$个进行代替,那么最终的答案会重复计算$(10-cnt)!$次。进行暴力枚举并统计答案后,除以$(10-cnt)!$即可。

B - Flowery Trails

从起点和终点进行两次最短路。开一个$dis[2][i]$数组,分别表示从$0$点到$i$点的最短路、从$n-1$点到$i$点的最短路。要判断一条边是否在最短路上,可以枚举每一条$单向边$,假设这条边的两个端点分别为$u$和$v$,如果满足$dis[0][u] + len + dis[1][v] = dis[0][n-1]$,那么从$u->v$方向的这条边就在最短路上,应该纳入统计。这个题可能会卡SPFA,所以使用了堆优化的DIJ

C - Golf Bot

使用FFT进行计数。使用$cnt$数组记录每个值是否出现。将$cnt$数组和自己进行卷积后(假设为$A$数组),$A[i]$的意义就是任意选两个存在的数进行求和后,和值为$i$的方案数。再将$A$数组加回到$cnt$数组。$cnt[i]$是否为$0$,就代表是否有方案至多选两个数,至少选一个数的和为i。

D - Book Club

最大流求是否有合法方案

给出一些给书的关系,问是否有方案,使得每个人可以交出一本书,并且获得一本书,不能自己和自己玩。

将一个人$i$看作两个点,编号$A_i$和$B_i$。从源点引边到每一个$A_i$点,容量为1,表示$i$这个人要交出一本书。从每一个$B_i$引一条边到汇点,容量为1,表示$i$这个人要获得一本书。如果有一个关系,$i$的书可以给$j$,那么连一条边从$A_i$到$B_j$。最后跑最大流,如果流量为n,就满足要求。

G - Playing With Geometry

离散化,坐标旋转。

给定两个图,以转角坐标的方式逆时针给出,问两个图的轮廓是否相似。允许进行压缩或者旋转。

直接将两个图的横纵坐标进行离散化(压缩)。枚举将第一图进行旋转,和第二个图进行匹配,匹配的时候,需要找到两张图最左下角的点,让后从这个点开始,逆时针匹配。如果每个坐标都是相同的,那么就是OK的。

I - The Safe Secret

循环枚举,区间DP

给一个由数字和运算符号组成的序列,长度为$2*n$运算符号只包含+-*和?,?可以任意替换为+-*。枚举将序列向左进行循环位移,每次位移$2$个单位,可以得到$n$个表达式序列,问这$n$个表达式的值的最小值和最大值的绝对值。

先将原始序列的数字和符号进行分离。再分别复制一份后接到后面。这样就可以进行区间dp了。注意,第i个数字就是$num[i]$了,它后面的符号就是$symbol[i]$。用$mx[i][j]$来表示从第$i$个数字到第$j$个数字组成的子区间的表达式的最大值,$mi[i][j]$表示最小值。初始化$mx[i][i] = mi[i][i] = num[i]$。枚举区间长度,枚举区间起点,再枚举区间内的断点,进行转移即可。要注意断点处为乘号的时候,并不是最小值*最小值就是最小值(考虑两个都是负数的情况),为了偷懒,直接暴力枚举了4种情况进行转移。

最后mx[i][n+i-1]和mi[i][n+i-1]就是第i个序列的表达式的最大值和最小值