[LuoguP2764] 最小路径覆盖问题

DAG 的最小路径点覆盖

给定有向图 。设 的一个简单路(顶点不相交的路)的集合。

如果 中每个顶点恰好在 的一条路上,则称 的一个路径覆盖。 中路径可以从 的任何一个顶点开始,长度也是任意的(可以为 0)。

的最小路径覆盖是 的所含路径条数最少的路径覆盖.

分析

将每个点 拆成 两个点,将 变成 . 显然这是一个二分图

在这个二分图上的任意匹配都构成集合 ,任意最大匹配都构成 的一个路径覆盖。

略证:原来 中的路径 在新的二分图 中被拆成了 组互不相交的边,即 组匹配;同理, 中的匹配也能反过来凑出若干条简单路径。证毕。

要求路径条数最少,等价于要求二分图中出度为 0 的点最少,等价于要求二分图中左部非匹配点最少,即最大匹配

因此,在 上求最大匹配即可。我们根据匹配的结果记录后继(或者前驱),即可输出方案。

路径的条数 = 最大匹配数

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=500,M=20000,INF=0x3f3f3f3f;
int n,m,s,t;

struct qxx{int nex,t,v;};
qxx e[M];
int cnt=1,h[N],cur[N];
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);}

int rk[N],pre[N];
bool bfs(){queue<int> q;
    memset(rk,0,sizeof(rk));
    memcpy(cur,h,sizeof(cur));
    q.push(s),rk[s]=1;
    while(q.size()){int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v);
        }
    }
    return rk[t];
}
int dinic(int u,int flow){if(u==t)return flow;
    int x,rest=flow;
    for(int i=h[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(!w||rk[v]!=rk[u]+1)continue;
        x=dinic(v,min(w,rest));
        if(x)e[i].v-=x,e[i^1].v+=x,rest-=x;
        else rk[v]=0;
        if(!rest)cur[u]=i;
    }
    if(rest)cur[u]=0;
    return flow-rest;
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){scanf("%d%d",&u,&v);
        add_flow(u,v+n,1);
    }
    s=0,t=n+n+1;
    for(int i=1;i<=n;i++){add_flow(s,i,1);
        add_flow(i+n,t,1);
    }
    int maxflow=0,suf[N],id[N]={0};
    while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;
    for(int u=1;u<=n;u++){for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(v==s||v==t||w)continue;
            suf[u]=v-n,id[v-n]++;// 对于每一条匹配边记录后继
        }
    }
    for(int u=1;u<=n;u++){if(id[u])continue;// 入度为 0 的点即为一条路径的开头
        for(int i=u;i;i=suf[i])printf("%d",i);
        puts("");
    }
    printf("%d",n-maxflow);
    return 0;
}

 上一篇
莫比乌斯反演小结 莫比乌斯反演小结
摘要 复习莫比乌斯反演~ 前言OI 的数论涉及求和的部分,一般采用 暴力计算;但是当上界过大的时候就需要考虑数论求和法。 常用的技巧有前缀和、差分、组合计数、等差数列求和、矩阵快速幂等,这些技巧都建立在数学原理的基础上 如果
2019.01.10
下一篇 
CFGoodBye2018 CFGoodBye2018
CF1091B平均数一下 #include<cstdio> #include<iostream> #define int long long using namespace std; int n,x,y; signed main
2018.12.31
  目录