ciniD TLE 91pts求助

P3376 【模板】网络最大流

Stinger @ 2021-04-09 19:53:07

本地一直跑不出来,离谱

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
    int to, nxt, cap;
} e[10005];
int head[205], dis[205], tot = 1, s, t;
bool mark[205];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int w) {
    e[++ tot].to = v, e[tot].cap = w, e[tot].nxt = head[u], head[u] = tot;
    e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}

bool bfs() {
    memset(dis, 0x3f, sizeof dis);
    memset(mark, 0, sizeof mark);
    dis[s] = 0;
    Q.push(s);
    while (Q.size()) {
        int u(Q.front());
        mark[u] = false;
        Q.pop();
        for (int i(head[u]); i; i = e[i].nxt) {
            int v(e[i].to);
            if (dis[u] + 1 < dis[v] && e[i].cap) {
                dis[v] = dis[u] + 1;
                if (!mark[v]) Q.push(v), mark[v] = true;
            }
        }
    }
    return dis[t] <= 1e9;
}

int dfs(const int u, const int low) {
    int flow(0);
    if (u == t) return low;
    for (int i(head[u]); i; i = e[i].nxt)
        if (dis[e[i].to] == dis[u] + 1 && e[i].cap) {
            int v(e[i].to);
            if (flow = dfs(v, min(low, e[i].cap))) {
                e[i].cap -= flow, e[i ^ 1].cap += flow;
                return flow;
            }
        }
    return 0;
}

int Dinic() {
    int flow(0), t(0);
    while (bfs())
        while (t = dfs(s, INF)) flow += t;
    return flow;
}

signed main()  {
//  freopen("P3376_9.in", "r", stdin);
    int n, m;
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    for (int i(1); i <= m; ++ i)  {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        if (u != v) AddEdge(u, v, w);
    }
    printf("%lld\n", Dinic());
    return 0;
}

|