原题链接

Description

求一个DAG的最小路径覆盖，并输出一种方案。

Solution

模板题啦~

Code

//「网络流 24 题」最小路径覆盖

#include <cstdio>

#include <cstring>

inline char gc()

{

    static char now[1<<16],*S,*T;

    if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}

    return *S++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

int const N=200+10;

int n,m; bool ed[N][N];

int link[N]; bool used[N];

bool find(int u)

{

    for(int v=1;v<=n;v++)

    {

        if(!ed[u][v]||used[v]) continue;

        used[v]=true;

        if(!link[v]||find(link[v])) {link[v]=u; return true;}

    }

    return false;

}

int pre[N],nxt[N];

int main()

{

    n=read(),m=read();

    for(int i=1;i<=m;i++) {int u=read(),v=read(); ed[u][v]=true;}

    int ans=n;

    for(int i=1;i<=n;i++)

    {

        memset(used,0,sizeof used);

        if(find(i)) ans--;

    }

    for(int i=1;i<=n;i++) pre[i]=link[i],nxt[link[i]]=i;

    for(int i=1;i<=n;i++)

    {

        if(pre[i]) continue;

        for(int u=i;u;u=nxt[u]) printf("%d ",u);

        printf("\n");

    }

    printf("%d\n",ans);

    return 0;

}