【网络流24题】最小路径覆盖问题

套路拆点。

路径覆盖实际上就是一开始全部用单个长度为0的路径覆盖。

然后尽可能多的地合并。

我们拆点成一个二分图，就变成\(最小边覆盖问题\)了

输出方案画个图就知道了。

上板子

/*
@Date    : 2019-07-29 10:41:00
@Author  : Adscn (adscn@qq.com)
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
int n,m;
const int MAXN=150*2+7,MAXM=6000+7+MAXN;
const int S=MAXN-2,T=S+1;
const int inf=2147483647;
struct edge{
    int v,nxt,flow;
}e[MAXM<<1|1];
int head[MAXN],cnt;
int cur[MAXN];
int vis[MAXN];
int dep[MAXN];
inline void add(int u,int v,int f){e[++cnt]=(edge){v,head[u],f},head[u]=cnt;}
inline void link(int u,int v,int f){add(u,v,f),add(v,u,0);}
inline void init(void){memset(head,cnt=-1,sizeof head);}
inline bool bfs(void)
{
    memset(dep,0,sizeof dep);
    static int Q[MAXN],l,r;
    dep[Q[l=r=0]=S]=1;
    while(l<=r)
        for(int p=Q[l++],i=head[p],v;~i;i=e[i].nxt)
            if(e[i].flow&&!dep[v=e[i].v])
                dep[v]=dep[p]+1,Q[++r]=v;
    return dep[T];
}
inline int dfs(int p,int restflow)
{
    if(p==T||restflow==0)return restflow;
    int sumflow=0;
    for(int &i=cur[p],v,flow;(~i)&&restflow;i=e[i].nxt)
        if(e[i].flow&&dep[v=e[i].v]==dep[p]+1&&(flow=dfs(v,min(e[i].flow,restflow))))
            restflow-=flow,sumflow+=flow,e[i].flow-=flow,e[i^1].flow+=flow;
    return sumflow;
}
inline int dinic()
{
    int maxflow=0;
    while(bfs())memcpy(cur,head,sizeof head),maxflow+=dfs(S,inf);
    return maxflow;
}
int main(void)
{
    #ifndef ONLINE_JUDGE
//  File("");
    #endif
    init();
    n=gi,m=gi;
    for(int i=1;i<=m;++i)
    {
        int u=gi,v=gi;
        link(u,v+n,1);
    }
    for(int i=1;i<=n;++i)link(S,i,1),link(i+n,T,1); 
    int tmp=dinic();
    vis[S]=1;
    for(int i=1;i<=n;++i)
        if(!vis[i])
        {
            int t=i;
            while(1)
            {
                pi(t,' ');
                vis[t]=1;
                bool flag=0;
                for(int j=head[t];~j;j=e[j].nxt)
                    if(!vis[e[j].v]&&!e[j].flow)
                        {
                            t=e[j].v;
                            flag=1;
                            break;
                        }
                if(!flag)break;
                t-=n;
            }
            putchar('\n');
        }
    pi(n-tmp);
    return 0;
}

【网络流24题】最小路径覆盖问题

原文：https://www.cnblogs.com/LLCSBlog/p/11263032.html