有源汇最大流

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int maxm = 4e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge{
    int to;
    int next;
    ll cap;
    ll flow;
};
Edge edge[maxm];
int head[maxn];
int tol;
void init(){
    tol = 0;
    memset(head, -1, sizeof(head));
}
namespace Nflows{
    int gap[maxn], dep[maxn], cur[maxn];
    int Q[maxn], s[maxn];
    void addedge(int u, int v, ll w, ll rw = 0){
        edge[tol].to = v;
        edge[tol].cap = w;
        edge[tol].flow = 0;
        edge[tol].next = head[u];
        head[u] = tol++;

        edge[tol].to = u;
        edge[tol].cap = rw;
        edge[tol].flow = 0;
        edge[tol].next = head[v];
        head[v] = tol++;
    }
    void bfs(int start, int end){
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        gap[0] = 1;
        int front = 0, rear = 0;
        dep[end] = 0;
        Q[rear++] = end;
        while(front != rear){
            int u = Q[front++];
            for(int i = head[u]; i != -1; i = edge[i].next){
                int v = edge[i].to;
                if(dep[v] != -1)    continue;
                Q[rear++] = v;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
            }
        } 
    }
    ll isap(int start, int end, int n){//n指点的个数
        bfs(start, end);
        memcpy(cur, head, sizeof(head));
        int top = 0;
        int u = start;
        ll ans = 0;
        while(dep[start] < n){
            if(u == end){
                ll Min = INF;
                int inser;
                for(int i = 0; i < top; i++){
                    if(Min > edge[s[i]].cap - edge[s[i]].flow){
                        Min = edge[s[i]].cap - edge[s[i]].flow;
                        inser = i;
                    }
                }
                for(int i = 0; i < top; i++){
                    edge[s[i]].flow += Min;
                    edge[s[i]^1].flow -= Min;
                }
                ans += Min;
                top = inser;
                u = edge[s[top]^1].to;
                continue;
            }
            bool flag = false;
            int v;
            for(int i = cur[u]; i != -1; i = edge[i].next){
                v = edge[i].to;
                if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                    flag = true;
                    cur[u] = i;
                    break;
                }
            }
            if(flag){
                s[top++] = cur[u];
                u = v;
                continue;
            }
            ll Min = n;
            for(int i = head[u]; i != -1; i = edge[i].next){
                if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){
                    Min = dep[edge[i].to];
                    cur[u] = i;
                }
            }
            gap[dep[u]]--;
            if(!gap[dep[u]])    return ans;
            dep[u] = Min + 1;
            gap[dep[u]]++;
            if(u != start)    u = edge[s[--top]^1].to;
        }
        return ans;
    }
}
int n, m;
int main(){
    while(scanf("%d%d", &n, &m) == 2)  {
        init();
        for(int i = 1; i <= n ;i++){
            int u, v;
            ll w;
            cin >> u >> v >> w;
            Nflows::addedge(u, v, w);
        }
        cout << Nflows::isap(1, m, m) << endl;
    }
}