USACO 5.4.3(最小割+拆点)

本题如果是删边就是裸最小割，但是是删点我们就要考虑拆点了。
我们把一个点$i$拆成$i$(入点)，$i+n$(出点)。
入点专门负责接受其他节点的入边，出点专门负责连出边。
然后我们使$i->i+n$，容量为1，意义为删掉一个点的需要的价值，这样就可以删点了
然后为了连通，如果原图$i->j$，那么就连$i+n->j, j+n->i$，容量为$INF$，因为这些边不能影响流量。
然后从$s+n$到$t$做最大流即为答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5, MAXM = 600 + 5, INF = 2147483647;
struct data {int v, cap, flow;};
vector<data> ed; 
vector<int> G[MAXN * 2];
int n, m, s, t; 
int en, cur[MAXN * 2], vis[MAXN * 2], d[MAXN * 2];
void ins(int u, int v, int c) {
    ed.push_back((data){v, c, 0}), G[u].push_back(en++);
    ed.push_back((data){u, 0, 0}), G[v].push_back(en++);
}
bool bfs() {
    queue<int> q;
    for (int i = 1; i <= n * 2; i++) vis[i] = false;
    vis[s] = true, d[s] = 0, q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
            if (!vis[v] && cap > flow) {
                vis[v] = true, d[v] = d[u] + 1, q.push(v);
            }
        }
    }
    return vis[t];
}
int dfs(int u, int a) {
    if (u == t) return a;
    if (a == 0) return 0;
    int retflow = 0;
    for (int &i = cur[u]; i < G[u].size(); i++) {
        int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
        if (cap > flow && d[v] == d[u] + 1) {
            int f = dfs(v, min(a, cap - flow));
            if (f > 0) {
                retflow += f, a -= f, ed[G[u][i]].flow += f, ed[G[u][i] ^ 1].flow -= f;
                if (a == 0) break;
            }
        }
    }
    return retflow;
}
int dinic() {
    int flow = 0;
    while (bfs()) {
        for (int i = 0; i <= n * 2; i++) cur[i] = 0;
        flow += dfs(s, INF);
    }
    return flow;
}
void clean() {
    en = 0;
    for (int i = 0; i <= n * 2; i++) G[i].clear();
    ed.clear();
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) ins(i, i + n, 1);
    for (int u, v, i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        ins(u + n, v, INF), ins(v + n, u, INF);
    }
    s += n;
    printf("%d\n", dinic());
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t), solve();
    return 0;
}