CF717G Underfail

传送门

传说之下欧耶

题意：给出一个长度 \(n\) 的字符串 \(s\)。
有 \(m\) 个单词 \(p_1\sim p_m\)，每一个有价值 \(a_i\)。
用这 \(m\) 个单词和 \(s\) 中的一些子串匹配，要求 \(s\) 的每个字符匹配次数 \(\le x\)，每个子串最多匹配一次。
每匹配上一个单词，总收益加上对应的价值。问最大总价值。数据范围三位数级别。

一道很神奇的建模题。

建立 \(n+2\) 个结点，\(S=1,T=n+2\)。然后 \(\forall i=1\sim n+1\)，\(i\) 向 \(i+1\) 连边，容量 \(x\) 费用 \(0\)。

对于一个能匹配上单词的子串 \(s[l\sim r]\)，令 \(l\) 向 \(r+1\) 连边，容量 \(1\) 费用为这个单词的价值。

跑最大费用最大流。

为什么是对的？我们可以把 \(i\rightarrow i+1\) 的一串看做是一条主路，由匹配上的单词加入的边是岔路。

如果一个流流过了岔路，就表示匹配了一个对应单词。岔路容量是 \(1\) 对应了一个子串只能匹配一次。

但每个字符匹配 \(\le x\) 怎么保证？因为每个岔路出来的流量最终都会回到主路上（有 \(n+2\) 的结点就是为了保证岔路到 \(n+1\) 依然可以汇入主路），所以如果一个位置匹配了超过 \(x\) 次，就一定会有超过 \(x\) 条岔路汇入主路，不可能。

真的是很神奇的建模。

如果我们试图在匹配的时候让对应子串的位置的容量 \(-1\)，会发现做不了。感性理解，因为每个单词的地位是相同的，所以我们无法让算法判断为什么在子串结束处就要离开；网络流里每条边也是相互独立的，没有办法做到把两条边匹配。