[BZOJ 3894] 文理分科 【最小割】
题目链接:BZOJ - 3894题目分析最小割模型,设定一个点与 S 相连表示选文,与 T 相连表示选理。那么首先要加上所有可能获得的权值,然后减去最小割,即不能获得的权值。那么对于每个点,从 S 向它连权值为它选文的价值的边,从它向 T 连权值为它选理的价值的边。对于一个点,它和与它相邻的点构成了一个集合,这个集合如果都选文,可以获得一个价值v1,如果都选理,可以获得一...