Monthly Archives: 7月 2015
HDU 2489 Minimal Ratio Tree
给出一个n个点的完全图每条边的边权和每个点的点权，选出m个点的一个子图，使子图的边权和/点权和最小
点数最多只有15个，可以枚举选取了哪些点。为使边权和最小，就是求这m个点组成的最小生成树，除上点权和，并维护商的最小值。
代码
HDU 2485 Destroying the bus stations
给出一个有向图，求最少去掉多少个点使的从S到T的最短距离大于K
如果问从S到T最少去掉多少条边使ST不连通，那么这就是个最小割的问题
把每个点拆成两个，连一条费用为0，流量为1的边，其余相连的两点连一条费用为1，流量为1的边。则每条增广路的费用为S-T的路长，S-T的费用大于K时停止增广，此时的最大流即为此图的最小割边数，原图的最小割点数
然而上面的想法是错的…
正解：枚举删除的点
Gyf's Blog 