网络流24题-最小路径覆盖

· · 题解

博大精深的网络流

P2764 最小路径覆盖问题

先AC再理解系列。。。

其实一条路径不一定非要有边吧。。。

那我们就假设开始时每个点都被以其自身为单独的顶点的路径覆盖（即起点与终点都是它）

在这个基础上缩减

每个点与其相反的点合

那为了区分点的出/入性质

将其拆成一个出点一个入点

限制条件就出来了：

故顶点之间容量为1且源汇到部集之间的容量也为1

所以相邻点之间在二分图上连边，容量为1

源汇分别与左/右部集（即出/入点）连容量为1的边

跑最小割（这里用最小割理解更形象）

输出n-最小割就行了

然后就完了


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=155,M=6000+5;
const int inf=0x7fffffff;
template<class T>inline void read(T &num){
    char ch;
    while(!isdigit(ch=getchar()));
    num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
}

int hea[N<<1],to[M<<2],nex[M<<2],val[M<<2],tot=1,n,m,s,t,vis[N<<1],dep[N<<1];

inline void add_edge(const int x,const int y,const int w){
    to[++tot]=y,nex[tot]=hea[x],hea[x]=tot,val[tot]=w;
}

queue<int> que;
bool bfs(){
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    while(que.size())que.pop();
    que.push(s);
    int x;
    while(que.size()){
        x=que.front();que.pop();
        for(int i=hea[x];i;i=nex[i]){
            int y=to[i];
            if(val[i]&&!dep[y]){
                dep[y]=dep[x]+1;
                if(y==t)return true;
                que.push(y);
            }
        }
    }
    return false;
}

int dfs(int x,int flow){
    if(x==t)return flow;
    int rest=flow,k;
    for(int i=hea[x];i&&rest;i=nex[i]){
        int y=to[i];
        if(val[i]&&dep[y]==dep[x]+1){
            k=dfs(y,min(rest,val[i]));
            if(k==0)dep[y]=0;
            val[i]-=k;
            val[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int dinic(){
    int maxflow=0,flow;
    while(bfs())while(flow=dfs(s,inf))maxflow+=flow;
    return maxflow;
}

int main(){
    read(n),read(m);
    s=n*2+2,t=n*2+1;
    for(int i=1,a,b;i<=m;++i){
        read(a),read(b);
        add_edge(a,b+n,1);
        add_edge(b+n,a,0);
    }
    for(int i=1;i<=n;++i){
        add_edge(s,i,1);
        add_edge(i,s,0);
        add_edge(i+n,t,1);
        add_edge(t,i+n,0);
    }
    int ans=n-dinic();
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            int fla=0;
            int x=i;
            int j;
            while(x!=t){
                for(j=hea[x];j;j=nex[j]){
                    if(!val[j]){
                        printf("%d ",x);
                        vis[x]=1;
                        fla=1;
                        if(to[j]==s)break;
                        x=to[j]-n;
                        break;
                    }
                }
                if(to[j]==s)break;
            }
            if(fla)printf("\n");
        }
    }
    printf("%d\n",ans);
    return 0;
}