OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2月前

08/30
16:52
OI

BZOJ3832

思路清奇的一道题
首先有向图的最长链可以通过添加超级源超级汇,计算超级源超级汇之间的最长路来实现
如果仅仅如此并不足以做这道题
这道题还用了最小割的思想
看大佬题解吧……不是很清楚这题要怎么讲明白

大佬题解的传送门

\(S\) 为超级源
\(T\) 为超级汇
\(g[i] \) 为 \(S\) 到 \(i\) 的最长路
\(f[i] \) 为 \(i\) 到 \(T\) 的最长路
\( edge={ From,To } \)
令一条边存在的贡献为 \( g[From]+f[To]+1 \)
这是这条边对最长路的贡献
我们维护两个点集 \( A,B \) 。一开始 \( A \) 中只有S,其余点都在 \(B\) 中。
我们用数据结构来维护两个集合之间的连边,注意这是一定包括了所有能从S到T的路径的。每次我们按照昂拓扑序从B中拿点到A中,在这个过程中维护边集即可
令被移动的点为 \(x\)
那么我们需要先把从 \(A\) 到 \(x\) 的边全部删除,即删除 \(x\) 的所有入边 【为什么?我们之前用的是拓扑序啊不是吗】
完成统计后再将 \(x\) 到 \(B\) 的边全部加入即可
同时为了保证一个点在被删除后,两端的点依然有贡献,我们要在一开始加入 \(f[x]\)
后面点 \(x\) 从B移动到A后,我们要把 \(f[x]\) 删除,再将 \(g[x]\) 加入边集。
某次删点之后我们选出来的边的贡献值中最大的最小,那么这就是我们要求的答案
值的维护随便挑个数据结构就做了
难点是边的值要怎么去想到
【算了反正我也是看题解的记住这个思路就好了】

代码:

BZOJ3832

@OceanEye6月前

05/9
21:15
OI

BZOJ4808

题目名字很有趣

但是看完题面会发现这就是个黑白染色最小割

网络流大法好,ISAP直接跑

好像这几道题是一个系列的233

 

BZOJ4808

@OceanEye6月前

05/2
20:04
OI

BZOJ1324

有些炸裂的题解

题目是一道最大点独立集,比较裸的那种

最大点独立集=最小点覆盖集的补集

然后套最小点覆盖集用sum-tot_flow即可

 

BZOJ1324

@OceanEye6月前

04/28
23:34
OI

BZOJ1497

最小割

从源点向每个人连收益大小的边

人向站连大小为INF的边

站向汇连大小为成本的边

这个时候的割有三种情况:

1.把收益割掉了,此时支出>收入

2.把支出割掉了,此时支出<收入

3.支出和收入同时割掉了,支出=收入

总的答案就是sum-割

 

BZOJ1497