输出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;
}