wllcjdst2026-09-16 21:26:14发布于:广东36阅读0回复0点赞复杂度超标的会标红,正常的标绿。 P3386 xi→1(yi+n)x_i\xrightarrow{1}(y_i+n)xi1(yi+n),s→1i(1≤i≤n)s\xrightarrow{1}i(1\le i\le n)s1i(1≤i≤n),i→1t(i≤i≤n)i\xrightarrow{1}t(i\le i\le n)i1t(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}isAii,i→Biti\xrightarrow{B_i}tiBit,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,2t,(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)。 有帮助,赞一个去预览0/2000发布全部评论 2yxdl1置顶秒删帖 2026-09-11 来自 浙江0yxdl1回复yxdl1怎么都是秒回大手子 2026-09-11 来自 浙江0cjdst回复yxdl1?!删删!? 2026-09-11 来自 广东0Xylophone置顶秒删帖 2026-09-11 来自 广东0cjdst回复Xylophone?!帖帖!? 2026-09-11 来自 广东0yxdl1回复cjdst!?贴贴?! 2026-09-11 来自 浙江0
有帮助,赞一个