P2740 [USACO4.2] 草地排水 Drainage Ditches

P2740 [USACO4.2] 草地排水 Drainage Ditches

大意

求最大流。

思路

板子。

代码

#include<bits/stdc++.h>
using namespace std;#define int long long
const int MAXN = 205;
const int MAXM = 205;
int n, m, S, T;struct node{int v, nxt, c;
}e[MAXM << 2];
int h[MAXN], d[MAXN], cur[MAXN];
int tot;void add(int u, int v, int c){e[tot] = {v, h[u], c};h[u] = tot ++;
}void init(){tot = 0;memset(h, -1, sizeof(h));
}bool bfs(){queue<int> q;memset(d, -1, sizeof(d));d[S] = 0;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == -1){d[v] = d[u] + 1;q.push(v);}}}return (d[T] == -1) ? false : true;
}int dfs(int u, int flow){if(u == T || !flow) return flow;int res = 0;for(int &i = cur[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == d[u] + 1){int tmp = dfs(v, min(flow, e[i].c));if(!tmp) continue;e[i].c -= tmp;e[i ^ 1].c += tmp;res += tmp;flow -= tmp;if(!flow) break;}}if(!res) d[u] = -1;return res;
}int Dinic(){int res = 0;while(bfs()){memcpy(cur, h, sizeof(h));res += dfs(S, 2e15);}return res;
}signed main(){init();int N, M;cin >> M >> N;S = 1, T = M;for(int i = 1; i <= N; i ++){int u, v, w; cin >> u >> v >> w;add(u, v, w); add(v, u, 0);}cout << Dinic() << endl;return 0;
}