FLOW3 最小路径覆盖问题

模型：

有向无环图最小路径覆盖->网络最大流

题意：

给定有向图 $G=(V,E)$。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。$P$ 中路径可以从 $V$ 的任何一个顶点开始，长度也是任意的，特别地，可以为 0。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。 求一个有向无环图 $G$ 的最小路径覆盖。

题解：

将“一条路径”看成本问题中的“流”

自然的，对图进行拆点操作，拆成进点和出点

题目要求两条路径无交点，也就是说每个点只有一个进或一个出，每条边也都只能经过一次

因此从源点向每个进点连条容量1的边，从每个出点向汇点连条容量1的边

对于每条读入的边$(u,v)$，从u的出点向v的进点连条容量1的边

跑遍最大流

最小路径覆盖数=点数-最大流

证明略去，个人认为这与“无环图中森林数=点数-边数”基本是一个道理

对于方案的输出，因为一条边只有选和不选两种选择，所以只需要在残量网络上跑一遍，将在同一个联通块中的点一起输出即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int oo=0x3f3f3f3f;
const int N=405,M=6e3+5;
int en=1,h[N],d[N],n,m,s,t,use,cur[N],ans;
bool v[N];

struct edge{
    int n,v,f;
}e[N+M<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

void exadd(int x,int y,int z){
    add(x,y,z);
    add(y,x,0);
}

bool bfs(int s,int aim){
    memset(d,0,sizeof d);
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].f){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].f){
            int flow=dfs(y,min(rest,e[i].f),aim);
            rest-=flow;
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}

void print(int x){
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==s||y==t) continue;
        if(e[i].f) continue;
        v[y-n-1]=1;
        putchar(' ');write(y-n-1);
        print(y-n);
    }
}

signed main(){
    read(n);read(m);
    s=1,t=n*2+2;
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        exadd(x+s,y+s+n,1);
    }
    for(int i=1;i<=n;i++) exadd(s,i+1,1),exadd(i+n+s,t,1);
    ans=n-dinic(s,t);
    for(int i=1;i<=n;i++) if(!v[i]){
        write(i);
        print(i+s);
        puts("");
    }
    write(ans);
}