SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ2768][JLOI2010]冠军调查(最大流 最高标号预流推进 + GAP优化)

这题很显然是一道最小割的题目,然后题目只要求最小割的容量,那么直接跑个最大流(关于最小割-最大流定理请自行谷歌),以前写过DINIC感觉不够高大上,然后果断来一个最高标号预流推进秀优越,事实上这个时间复杂度的确很优秀。一开始我写的没加GAP优化,400+ms,跑得比DINIC还慢,真是不爽,下午看到了一种叫GAP优化的东西,加上之后就28ms了,怒刷到rank2。     Read more