落谷p3376 最大流EdmondsKarp增广路模板

参考:

https://blog.csdn.net/txl199106/article/details/64441994

分析：

该算法是用bfs求出是否有路从s到t， 然后建立反向边（关于反向边）， 最终求出答案， 复杂度(mn)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000 + 7;
const int MAXM = 100000 + 7;
const int MAX_INT = (1 << 30);

struct Edge {
    int v, nxt, w;
};

struct Node {
    int v, id;
};

int n, m, ecnt, S , T; // n , m , S , T 点，边，源点，汇点
bool vis[MAXN];
int head[MAXN];
Node pre[MAXN];
Edge edge[2 * MAXM];

void init() {
    ecnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w) {
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool bfs(int s, int t) {
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s].v = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int i = head[u]; i + 1; i = edge[i].nxt) {
            int v = edge[i].v;
            if(!vis[v] && edge[i].w) {
                pre[v].v = u;
                pre[v].id = i;
                vis[v] = true;
                if(v == t)
                    return true;
                que.push(v);
            }
        }
    }
    return false;
}

int EK(int s, int t) {
    int ans = 0;
    while(bfs(s, t)) {
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i].v) {
            mi = min(mi, edge[pre[i].id].w);
        }
        for(int i = t; i != s; i = pre[i].v) {
            edge[pre[i].id].w -= mi;
            edge[pre[i].id ^ 1].w += mi; //异或1的用处是 偶数+1， 奇数-1 （两条正反向边是相邻的
        }
        ans += mi;
    }
    return ans;
}

int main() {
    freopen("1.txt","r", stdin);
    init();
    ios::sync_with_stdio(false);
    cin >> n >> m >> S >> T;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, 0);
    }
    // 调用
    cout << EK(S, T) << "
";
}
// 加边