最大流=最小割

ISAP最大流+指针存图

建图

  • 把原图每一个节点$i$拆成入点$i$和出点$i + n$,设超级源点为$0$,超级汇点为$n \times 2 + 1$
  • 对于$\forall i \in [1, n]$,从$0$向$i$连边,容量$1$
  • 对于$\forall i \in [1, n]$,从$i + n$向$n \times 2 + 1$连边,容量$1$
  • 对于输入一条边$u \to v$,从$u$向$v + n$连边,容量$1$

输出

我们要找到没被割掉并且是一条路径起点的点,然后递归输出这条路径,具体见代码

最终路径数为$n - maxflow$

代码

// luogu-judger-enable-o2
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 65;
const int MAXM = 6e3 + 5;
const int INF = 0x3f3f3f3f;

int n, m;

struct Edge{
    int to, val;
    Edge *nxt, *ops;
    Edge(int to, int val, Edge *nxt): to(to), val(val), nxt(nxt) {}
};

namespace ISAP{
    Edge *head[MAXN << 1], *cur[MAXN << 1];
    int s, t, dep[MAXN << 1], gap[MAXN << 1], res;
    
    void AddEdge(int u, int v, int w) {
        head[u] = new Edge(v, w, head[u]);
        head[v] = new Edge(u, 0, head[v]);
        head[v]->ops = head[u]; head[u]->ops = head[v];
    }
    
    void Bfs() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        dep[t] = 0; gap[dep[t]]++;
        queue<int> q; q.push(t);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (Edge *e = head[u]; e; e = e->nxt) {
                int v = e->to;
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
                q.push(v);
            }
        }
    }
    
    int Dfs(int u, int flow) {
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *e = head[u]; e; e = e->nxt) {
            int v = e->to;
            if (e->val && dep[v] == dep[u] - 1) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    e->val -= mi;
                    e->ops->val += mi;
                    used += mi;
                }
                if (used == flow) return used;
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = n * 2 + 3;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }
    
    void Work() {
        res = 0;
        Bfs();
        while (dep[s] <= n << 1) Dfs(s, INF);
    }
    
    void Print(int u) {//输出路径
        cout << u << ' ';
        for (Edge *e = head[u]; e; e = e->nxt) {
            int v = e->to;
            if (e->val == 0 && v > n && v <= n << 1) {
                Print(v - n);
                return;
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    ISAP :: s = 0; ISAP :: t = n * 2 + 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        ISAP :: AddEdge(x, y + n, 1);
    }
    for (int i = 1; i <= n; i++) {
        ISAP :: AddEdge(0, i, 1);
        ISAP :: AddEdge(i + n, n * 2 + 1, 1);
    }
    ISAP :: Work();
    /*for (Edge *e = ISAP :: head[0]; e; e = e->nxt) {
        if (e->val == 0) ISAP :: Print(e->to), cout << endl;
    }*/
    //for (int i = 1; i <= n; i++) if (!nots[i]) ISAP :: Print(i), cout << endl;
    for (int i = 1; i <= n; i++) {//找起点
        bool ff = false;
        for (Edge *e = ISAP :: head[i + n]; e; e = e->nxt) {
            int v = e->to;
            if (e->val && v >= 1 && v <= n) {
                ff = true;
                break;
            }
        }
        if (!ff) ISAP :: Print(i), cout << endl;
    }
    cout << n - ISAP :: res << endl;
    return 0;
}

反抄袭自寻