P2764 最小路径覆盖问题

问题描述：

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

提示：设\(V={1,2,.... ,n}\),构造网络\(G_1=(V_1,E_1)\)

如下：

\(V_1=\{x_1,x_2,...,x_n\}\cup\{y_1,y_2,...y_n\}\)

\(E_1=\{(x_0,x_i):i\in V\}\cup\{(y_0,y_i):i\in E \}\cup\{(x_i,y_j):(i,j)\in E\}\)

即每条边的容量均为1。求网络\(G_1\)最大流。

输入输出格式

输入格式：

件第1 行有2个正整数\(n\)和\(m\)。\(n\)是给定有向无环图\(G\) 的顶点数，\(m\)是\(G\) 的边数。接下来的\(m\)行，每行有\(2\) 个正整数\(i\)和\(j\)，表示一条有向边\((i,j)\)。

输出格式：

从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。

说明

\(1<=n<=150,1<=m<=6000\)

由@zhouyonglong提供SPJ

---

其实提示说的很清楚了。

这里用我自己的感性语言解释一下。

描述：将图中每个点拆成两个，分成两个图。把连原来的边连上。跑二分图匹配，最小路径数=总点数-最大匹配数。

解释：

不难发现，路径数+路径集合中边的数量=总点数。(肽链)

总点数不变，我们就可以转化到求最大的边的数量。

而对于原图中的每一个点\(i\),都可以分成以下四中情况。

为了使边的数量尽量大，我们应该多令情况(3)出现。

而这几种情况中又一个点最多戳某一个点屁股，也只能被最多被一个戳。

那么，劈配？ 匹配？

再看看我们跑的二分图是什么，是不是很明了~

---

CODE:

#include <cstdio>

#include <cstring>

const int N=160;

int n,m;

struct edge

{

    int to,next;

}g[N*N];

int head[N],cnt=0;

void add(int u,int v)

{

    g[++cnt].to=v;

    g[cnt].next=head[u];

    head[u]=cnt;

}

int used[N],match[N];

bool m_find(int u)

{

    for(int i=head[u];i;i=g[i].next)

    {

        int v=g[i].to;

        if(!used[v])

        {

            used[v]=1;

            if(!match[v]||m_find(match[v]))

            {

                match[v]=u;

                return true;

            }

        }

    }

    return false;

}

void dfs(int now)

{

    if(!match[now]) {printf("%d ",now);return;}

    dfs(match[now]); printf("%d ",now);

}

int main()

{

    scanf("%d%d",&n,&m);

    int u,v;

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

    {

        scanf("%d%d",&u,&v);

        add(u,v);

    }

    int ans=0;

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

    {

        memset(used,0,sizeof(used));

        if(m_find(i)) ans++;

    }

    memset(used,0,sizeof(used));

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

        used[match[i]]=1;

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

        if(!used[i])

        {dfs(i);printf("\n");}

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

    return 0;

}

---

2018.5.6