46分TLE求调

P3376 【模板】网络最大流

yyy_2013 @ 2023-03-22 20:28:16

// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 1e18

int s, t;
vector<pair<int, ll> > graph[205];
bool vis[205];
int p[205];

ll bfs() {
    memset(vis, 0, sizeof vis);
    queue<pair<int, ll> > que;
    que.emplace(s, INF);
    p[s] = -1;
    vis[s] = 1;
    while (que.size()) {
        int x = que.front().first;
        ll mx = que.front().second;
        que.pop();
        if (x == t) {
            do {
                int pa = p[x];
                for (auto & pr : graph[pa]) {
                    int adj = pr.first;
                    if (adj != x) {
                        continue;
                    }
                    pr.second -= mx;
                }
                for (auto & pr : graph[x]) {
                    int adj = pr.first;
                    if (adj != pa) {
                        continue;
                    }
                    pr.second += mx;
                }
            } while ((x = p[x]) != -1);
            return mx;
        }
        for (auto pr : graph[x]) {
            int adj = pr.first;
            ll cost = pr.second;
            if (vis[adj] || cost == 0) {
                continue;
            }
            vis[adj] = 1;
            p[adj] = x;
            que.emplace(adj, min(mx, cost));
        }
    }
    return 0;
}

int main() {
    int n, m;
    scanf("%d %d %d %d", &n, &m, &s, &t);
    s--, t--;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        u--, v--;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, 0);
    }
    ll ans = 0, x;
    while ((x = bfs())) {
        ans += x;
    }
    printf("%lld", ans);
    return 0;
}

|