题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式
第一行包含四个正整数 n nn,m mm,s ss,t tt，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数 ui ,vi,wi ，表示第 i 条有向边从 ui 出发，到达 vi，边权为 wi即该边最大流量为 wi）。
输出格式
一行，包含一个正整数，即为该网络的最大流。
输入输出样例
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40
50
样例输入输出 1 解释
struct Edge { int u, v; ll cap, flow; Edge(int _u, int _v, ll _cap, ll _flow) { u = _u, v = _v, cap = _cap, flow = _flow; } }; struct ISAP { vector<Edge> edge; vector<int> G[maxn]; ll dis[maxn], cur[maxn]; int n, s, t; ll p[maxn], num[maxn]; bool vis[maxn]; void init(int _n, int _s, int _t) { this->n = _n, this->s = _s, this->t = _t; for (int i = 1; i <= _n; i++) G[i].clear(); edge.clear(); } void add(int u, int v, ll cap) { edge.push_back(Edge(u, v, cap, 0)); edge.push_back(Edge(v, u, 0, 0)); int siz = edge.size(); G[u].push_back(siz - 2); G[v].push_back(siz - 1); } void BFS() { for (int i = 1; i <= n; i++) dis[i] = n; queue<int> que; que.push(t); dis[t] = 0; while (que.size()) { int u = que.front(); que.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edge[G[u][i]]; if (e.cap <= e.flow && dis[e.v] == n) { que.push(e.v); dis[e.v] = dis[u] + 1; } } } } ll Augment() { ll x = t, a = 0x3f3f3f3f; while (x != s) { Edge &e = edge[p[x]]; a = min(a, e.cap - e.flow); x = edge[p[x]].u; } x = t; while (x != s) { edge[p[x]].flow += a; edge[p[x] ^ 1].flow -= a; x = edge[p[x]].u; } return a; } ll MaxFlow() { ll flow = 0LL; ///bfs();//wa BFS();//ac memset(num, 0, sizeof num); for (int i = 0; i <= n; i++) num[dis[i]]++; int x = s; memset(cur, 0, sizeof cur); while (dis[s] < n) { if (x == t) { flow += Augment(); x = s; } int ok = 0; for (int i = cur[x]; i < G[x].size(); i++) { Edge &e = edge[G[x][i]]; if (e.cap > e.flow && dis[x] == dis[e.v] + 1) { ok = 1; p[e.v] = G[x][i]; cur[x] = i; x = e.v; break; } } if (!ok) { ll m = n - 1; for (int i = 0; i < G[x].size(); i++) { Edge &e = edge[G[x][i]]; if (e.cap > e.flow) m = min(m, dis[e.v]); } if (--num[dis[x]] == 0) break; num[dis[x] = m + 1]++; cur[x] = 0; if (x != s) x = edge[p[x]].u; } } return flow; } } solve; int main() { int n = read, m = read, s = read, t = read; solve.init(n, s, t); for (int i = 1; i <= m; i++) { int u = read, v = read; ll cap = read; solve.add(u, v, cap); } cout << solve.MaxFlow() << endl; return 0; }
