P2764 最小路径覆盖问题

典型的有向无环图求最小路径点覆盖,要求我们选出若干个简单路径,将所有的的点覆盖,且路径之间不能相交,求最少的路径条数...

我们考虑一个路径覆盖,每个点由于都被覆盖,所以他的入度，出度必然有一个为1.且最大为1.

我们之后考虑将每个点拆点,分成入度与出度两部分,分到两侧.当有一条边(x,y)时,我们将x的出度连向y的入度.

路径覆盖中的每条边,在二分图中构成一组匹配,

考虑每条路径的起点,入度为0,终点,出度为0,分别与入度点,出度点的非匹配点相对应.

由于求最少的路径覆盖.也就是求最少的起点（终点）->最少的非匹配点)->n-最多的匹配点->n-最大匹配.

故ADG的最小路径点覆盖=n-拆点二分图的最大匹配.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=310,M=12010;
int link[N],tot,n,m,matchx[N],matchy[N],ans;
bool vis[N];
struct edge{int y,next;}a[M<<1];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline void add(int x,int y)
{
    a[++tot].y=y;a[tot].next=link[x];link[x]=tot;
}
inline bool find(int x)
{
    for(int i=link[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(!vis[y])
        {
            vis[y]=1;
            if(!matchy[y]||find(matchy[y])) 
            {
                matchy[y]=x;
                matchx[x]=y;
                return true;
            }
        }
    }
    return false;
}
inline void dfs(int x)
{
    int y=matchx[x]-n;
    if(y<1) return;
    cout<<y<<' ';
    if(!vis[y]&&matchx[y]) vis[y]=1,dfs(y);
}
int main()
{
    freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        add(x,y+n);
    }
    for(int i=1;i<=n;++i)
    {
        memset(vis,0,sizeof(vis));
        if(find(i)) ans++;
    }
    //for(int i=1;i<=n;++i) cout<<matchx[i]-n<<endl;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i)
    {
        if(!vis[i]&&matchx[i]) 
        {
            cout<<i<<' ';
            vis[i]=1;
            dfs(i);
            puts("");
        }
    }
    cout<<n-ans<<endl;
    return 0;
}

View Code