最终得对抗自己

Categories » 网络流

[POJ 3155] Hard Life 最大密度子图

给定无向图,点有点权,边有边权,一条边被选中当且仅当这条边链接的两个点被选中,现在求一个联通子图让所有被选中点权值之和除以被选中边的权值之和最小。

这就是最大密度子图问题了。

[UVA 11248] Frequency Hopping

给个带权无向图,求能不能修改一条边流量到INF来让1到N的最大流达到C,能的话输出方案。

常数未优化系列。

[BZOJ 1324] Exca王者之剑 最大流

网络流题目…
TM 是套路…

[BZOJ 1565][NOI2009]植物大战僵尸 最小割

网络流建模题目题目, 关键在于利用最小割转换和Infinite边限制。
题面略长我就不放在摘要里了。。。