不是哥们,怎么连样例都过不去啊
查看原帖
不是哥们,怎么连样例都过不去啊
22716
神仙酱楼主2024/5/20 23:21

输出0,isap,建图和题解一样,板子也没错。

#include <bits/stdc++.h>

using namespace std;
const int N = 110 * 2, M = 1210 * 3, INF = 0x3f3f3f3f;
int n, m, s, t, maxflow;
int dep[N], gap[N], cur[N], h[N], nxt[M], e[M], w[M], idx = 2;
namespace details {
    void add(int a, int b, int c) {
        e[idx] = b, w[idx] = c, nxt[idx] = h[a], cur[a] = h[a] = idx++;
    }

}  // namespace details
void add(int a, int b, int c) {
    details::add(a, b, c), details::add(b, a, 0);
}
void bfs() {
    queue<int> q;
    q.push(t);
    memset(dep, -1, sizeof dep);
    dep[t] = 0, gap[0] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i; i = nxt[i]) {
            int j = e[i];
            if (dep[j] == -1) {
                ++gap[dep[j] = dep[u] + 1];
                q.push(j);
            }
        }
    }
}

int dfs(int u, int flow) {
    if (u == t)
        return flow;
    int used = 0;
    for (int i = h[u]; i; i = nxt[i]) {
        cur[u] = i;
        int j = e[i];
        if (dep[j] == dep[u] - 1 && w[i] > 0) {
            int f = dfs(j, min(w[i], flow - used));
            used += f;
            w[i] -= f, w[i ^ 1] += f;
            if (used == flow)
                return cur[u] = h[u], flow;
        }
    }
    cur[u] = h[u];
    if (!--gap[dep[u]])
        dep[s] = n * 2;
    ++gap[++dep[u]];
    return used;
}

void isap() {
    bfs();
    while (dep[s] < n * 2)
        maxflow += dfs(s, INF);
}
                                    
signed main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; ++i)
        if (i != s && i != t)
            add(i, i + n, 1);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b + n, INF), add(a + n, b, INF);
    }
    isap();
    cout << maxflow << "\n";

    return 0;
}

2024/5/20 23:21
加载中...