洛谷2764：[网络流24题]最小路径覆盖问题—

洛谷2764：[网络流24题]最小路径覆盖问题——题解

阅读量：7064 次

发布时间：2019-06-28

本文共 2050 字，大约阅读时间需要 6 分钟。

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

设计一个有效算法求一个有向无环图G 的最小路径覆盖。

因为是有向无环图所以可以二分图匹配，匹配出最小点覆盖即可。

注意网络流求的时候反边走的时候不能乱更新啊！因为这个错了半天。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=501;const int M=50010;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int nxt,to,w;}edge[M];int head[N],cnt=-1,S,T,nxt[N];inline void add(int u,int v,int w){ edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; edge[++cnt].to=u;edge[cnt].w=0;edge[cnt].nxt=head[v];head[v]=cnt;}int lev[N],cur[N],dui[N];bool bfs(int m){ int r=0; for(int i=1;i<=m;i++){ lev[i]=-1; cur[i]=head[i]; } dui[0]=S,lev[S]=0; int u,v; for(int l=0;l<=r;l++){ u=dui[l]; for(int e=head[u];e!=-1;e=edge[e].nxt){ v=edge[e].to; if(edge[e].w>0&&lev[v]==-1){ lev[v]=lev[u]+1; r++; dui[r]=v; if(v==T)return 1; } } } return 0;}int dinic(int u,int flow,int m){ if(u==m)return flow; int res=0,delta; for(int &e=cur[u];e!=-1;e=edge[e].nxt){ int v=edge[e].to; if(edge[e].w>0&&lev[u]
            
             0){ edge[e].w-=delta; edge[e^1].w+=delta; res+=delta; nxt[u]=v; if(res==flow)break; } } } if(res!=flow)lev[u]=-1; return res;}int main(){ memset(head,-1,sizeof(head)); int n=read(),m=read(); S=n*2+1,T=S+1; for(int i=1;i<=m;i++){ int u=read(),v=read(); add(u,v+n,1); } for(int i=1;i<=n;i++){ add(S,i,1); add(i+n,T,1); } int ans=n; while(bfs(T))ans-=dinic(S,INF,T); for(int i=1;i<=n;i++){ if(nxt[i]){ int t=i; do{ if(t>n)t-=n; printf("%d ",t); int x=nxt[t]; nxt[t]=0; t=x; }while(t); puts(""); } } printf("%d\n",ans); return 0;}