洛谷(最小路径覆盖问题)

链接：https://www.luogu.org/problemnew/show/P2764
思路：最小路径覆盖问题分为最小不相交路径覆盖（每个顶点只能经过一次）和最小相交路径覆盖（定点可以经过多次）。后者做一次floyd传递闭包就变成了前者。而前者需要拆点，将每个点x拆为两个点x1，x2，x1作为二分图的左边点，x2作为二分图的右边点，然后建立一个超级源点和超级汇点，跑一遍最大流，最后用顶点数目（最初的）n-最大流就是最小路径的数目。（证明：一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。）
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int maxn = 300;
const int INF = 1e9;
int vis[maxn];
int nexto[maxn];

struct edge{
    int from,to,cap,flow;
};

struct Dinic{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n){
        this->n = n;
        edges.clear();
        for(int i=0;i<=n;i++)G[i].clear();
    }

    void addedge(int from,int to,int cap){
        edges.push_back(edge{from,to,cap,0});
        edges.push_back(edge{to,from,0,0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                edge &e = edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t||a==0)return a;
        int flow = 0,f;
        for(int &i = cur[x];i<G[x].size();i++){
            edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int maxflow(int s,int t){
        this->s = s;
        this->t = t;
        int flow = 0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }
}solver;

int main(){
    scanf("%d%d",&n,&m);
    solver.init(2*n+1);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        solver.addedge(a,b+n,1);
    }
    for(int i=1;i<=n;i++){
    solver.addedge(0,i,1);
    solver.addedge(i+n,2*n+1,1);
    }
    int res = n - solver.maxflow(0,2*n+1);
    for(int i=0;i<solver.edges.size();i+=2){//这样遍历的都是反向边
        edge e = solver.edges[i];
        if(e.flow)nexto[e.from] = e.to>n?e.to-n:e.to;
    }
    for(int i=1;i<=n;i++){
        int u = i;
        if(!vis[u]){
            while(u){
                vis[u] = 1;
                printf("%d ",u);
                u = nexto[u];
            }
            printf("\n");
        }
    }
    printf("%d\n",res);
    return 0;
}