HDU 3251 Being a Hero (最小割)

HDU 3251 Being a Hero (最小割)

题目链接:点我~~ 题意:n个点m条边的有向图,f个可选城市,每个城市都有其价值w,国王的城市在1,要分配一些城市,分配的原则是:只能在规定的f个城市中选若干个,这f个城市每个都有一个价值,被选择的城市要与城市1隔离,所以需要花费一些费用来破坏边。问能获取到的最大利益,以及要破坏的边。 思路:求能获取的最大利益,先建立一个超级汇点,将f个可选城市与汇点连接,...
10月03日 2,060
HDU 5889 Barricade (最短路+最小割)

HDU 5889 Barricade (最短路+最小割)

题目链接:点我~~ 题意:1000个点10000条边的无向图,敌人从n走一条最短路到1,在第i条路设置障碍的代价是wi,求最少的代价使得敌人至少会遇到一次障碍。 思路:先确定最短路,然后在最短路径上跑一个网络流,即可求出最小割。 #include <bits/stdc++.h> using namespace std; typedef lon...
09月23日 2,125
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40