网络流24题之三最小路径覆盖问题

内容

填坑

题目描述

«问题描述：

给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。提示：设V={1，2，…. ，n}，构造网络G1=(V1,E1)如下：

每条边的容量均为1。求网络G1的（ 0 x , 0 y ）最大流。

«编程任务：

对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

1 4 7 10 11
2 5 8
3 6 9
3

说明

1<=n<=150,1<=m<=6000

模型：

有向无环图最小路径覆盖，可以转化成二分图最大匹配问题，从而用最大流解决。

实现：

构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。

最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。

分析：

对于一个路径覆盖，有如下性质：

1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 – 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 2001412
#define N 5100
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
struct node
{
    int from,to,next,flow;
}e[M];
int tot=-1,st[M],dis[N],q[N][2],make[N],vis[N];
int n,m,x,y,z;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
int bfs(int s,int t)
{
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=st[x];~i;i=e[i].next)
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            make[x]=e[i].to;
            return ans;
        }
    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
main()
{
    scanf("%d%d",&n,&m);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),add(x,y+n,0x3f3f3f3f),add(y+n,x,0);
    for (int i=1;i<=n;i++)
        add(0,i,1),add(i,0,0);
    for (int i=n+1;i<=2*n;i++)
        add(i,2*n+1,1),add(2*n+1,i,0);
    int ans=Dinic(0,2*n+1);
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            if (make[i])
            {
                int j=i;
                while(j!=2*n+1)
                {
                    vis[j]=1;
                    printf("%d ",j);
                    if (!make[j]) break;
                    j=make[j]-n;
                }
            }
            puts("");
        }
    printf("%d\n",n-ans);
}

网络流24题之三 最小路径覆盖问题

题目描述

输入输出格式

输入输出样例

说明

网络流24题之三最小路径覆盖问题