OceanEye's Blog

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

@OceanEye3月前

05/9
21:15
OI

BZOJ4808

题目名字很有趣

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

网络流大法好,ISAP直接跑

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

 

BZOJ4808

@OceanEye4月前

05/2
20:04
OI

BZOJ1324

有些炸裂的题解

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

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

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

 

BZOJ1324

@OceanEye4月前

04/28
23:34
OI

BZOJ1497

最小割

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

人向站连大小为INF的边

站向汇连大小为成本的边

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

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

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

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

总的答案就是sum-割

 

BZOJ1497