复杂度超标的会标红,正常的标绿。
P3386
xi→1(yi+n)x_i\xrightarrow{1}(y_i+n)xi 1 (yi +n),s→1i(1≤i≤n)s\xrightarrow{1}i(1\le i\le n)s1 i(1≤i≤n),i→1t(i≤i≤n)i\xrightarrow{1}t(i\le i\le n)i1 t(i≤i≤n),flow(s,t)\text{flow}(s,t)flow(s,t)。
O(en+m)\green{O(e\sqrt{n+m})}O(en+m )。
P1361
看到类似二分图(分组的规模为 222)。考虑把 sss 看作分到第一组,分到第二组看作 ttt,跑最小割。
s→Aiis\xrightarrow{A_i}isAi i,i→Biti\xrightarrow{B_i}tiBi t,s→Ci,1(n+2i−1)s\xrightarrow{C_{i,1}}(n+2i-1)sCi,1 (n+2i−1),(n+2i)→Ci,2t(n+2i)\xrightarrow{C_{i,2}} t(n+2i)Ci,2 t,(n+2i−1)→+∞Pi,j(n+2i-1)\xrightarrow{+\infty} P_{i,j}(n+2i−1)+∞ Pi,j ,Pi,j→+∞(n+2i)P_{i,j}\xrightarrow{+\infty}(n+2i)Pi,j +∞
(n+2i),cut(s,t)\text{cut}(s,t)cut(s,t)。
O(n3m)\red{O(n^3m)}O(n3m)。