- 1
- /*
- 2 ID:ivorysi
- 3 PROG:ditch
- 4 LANG:C++
- 5 */
- 6#include 7#include 8#include 9#include 10#include < set > 11#include 12#define inf 0x7fffffff 13#define ivorysi 14#define siji(i, x, y) for (int i = x; i <= y; ++i) 15#define gongzi(j, x, y) for (int j = x; j >= y; --j) 16#define xiaosiji(i, x, y) for (int i = x; i17#define sigongzi(j, x, y) for (int j = x; j > y; --j) 18 using namespace std; 19 struct node {
- 20 int to,
- next,
- val;
- 21
- }
- edge[505]; 22 int head[305], sum = 1; 23 void add(int u, int v, int c) {
- 24 edge[++sum].to = v;
- 25 edge[sum].next = head[u];
- 26 edge[sum].val = c;
- 27 head[u] = sum;
- 28
- }
- 29 void AddTwoWays(int u, int v, int c) {
- 30 add(u, v, c);
- 31 add(v, u, 0); //反向边
- 32
- }
- 33 int n, m, dis[305], gap[305], ans; 34 int sap(int u, int aug) { //O(玄学)
- 35
- if (u == m) return aug;
- 36 int dmin = m - 1,
- flow = 0,
- v,
- t;
- 37 38
- for (int i = head[u]; i; i = edge[i].next) {
- 39 v = edge[i].to;
- 40
- if (edge[i].val > 0) { //只有还能流动的地方才能分层
- 41
- if (dis[u] == dis[v] + 1) {
- 42 t = sap(v, min(aug - flow, edge[i].val)); //限制流量不超过该点流量和边的限制
- 43 edge[i].val -= t;
- 44 edge[i ^ 1].val += t;
- 45 flow += t;
- 46
- if (aug == flow) return flow; //流尽
- 47
- if (dis[1] >= m) return flow; //搜索已在某处达到结束条件
- 48
- }
- 49 dmin = min(dmin, dis[v]);
- 50
- }
- 51
- }
- 52
- if (!flow) {
- 53--gap[dis[u]];
- 54
- if (gap[dis[u]] == 0) dis[1] = m; //出现断层说明无法再流
- 55 dis[u] = dmin + 1; //分层
- 56++gap[dis[u]];
- 57
- }
- 58
- return flow;
- 59
- }
- 60 int main(int argc, char const * argv[]) 61 {
- 62#ifdef ivorysi 63 freopen("ditch.in", "r", stdin);
- 64 freopen("ditch.out", "w", stdout);
- 65#
- else 66 freopen("f1.in", "r", stdin);
- 67#endif 68 scanf("%d%d", &n, &m);
- 69 int u,
- v,
- c;
- 70 siji(i, 1, n) {
- 71 scanf("%d%d%d", &u, &v, &c);
- 72 AddTwoWays(u, v, c);
- 73
- }
- 74
- while (dis[1] 1, inf);
- }
- 75 printf("%d\n", ans); 76
- return 0; 77
- }
来源: