【Luogu P2764】最小路径覆盖问题

Author Avatar
洛水·锦依卫 1月 28, 2019

【Luogu P2764】最小路径覆盖问题

网络流 $24$ 题之一。

Topic

Description

给出一个 $n$ 个点 $m$ 条边的 $DAG$ ,求最小路径点覆盖,并输出路径选择方案。

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例1

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

输出样例1

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

说明

$1\leq n\leq 150,1\leq m\leq 6000$

思路

这题其实就是 $DAG$ 上的最小路径点覆盖,详情参考这篇 $blog$

其实这里只要叙述怎么处理方案的输出就好了 ……

我们对于二分图跑完最大流之后,扫一遍二分图中所有的边 (并不包括连向超级源点汇点的边) ,根据网络流残余网络的特性,如果某一条边的反边中剩余容量不为 $0$ ,那么它必定是最大流中的一条可行弧。则我们记录下这条边,对于左侧点 $i$ ,记录一个 $next[i]$ 代表 $i$ 连向的边,并记录右侧点 $j’$ 是否被经过。接着,我们扫一遍右边的点,如果 $i’$ 没有被任何一条边经过,则入度为 $0$ ,必定为路径起点,那么我们从 $i$ 开始借助 $next$ 数组遍历这条路径并输出即可。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,S,T;
int head[1001],nx[20001],to[20001],w[20001],cnt;
int deep[1001],nt[1001];
bool book[20001],r[1001];
int inf=1e9,ans;
void add(int u,int v,int W,int d)
{
    to[d]=v,nx[d]=head[u],w[d]=W;
    head[u]=d;
}
queue <int> q;
bool init()
{
    memset(book,0,sizeof(book));
    memset(deep,-1,sizeof(deep));
    deep[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nx[i])
            if(deep[to[i]]==-1&&w[i]>0)
            {
                deep[to[i]]=deep[x]+1;
                q.push(to[i]);
            }
    }
    return deep[T]!=-1;
}
int dfs(int x,int limit)
{
    if(x==T||!limit)return limit;
    int flow=0,fnow;
    for(int i=head[x];i;i=nx[i])
        if(deep[to[i]]==deep[x]+1&&!book[i]&&(fnow=dfs(to[i],min(limit,w[i]))))
        {
            book[i]=true;
            flow+=fnow;
            limit-=fnow;
            w[i]-=fnow;
            w[i^1]+=fnow;
            if(!limit)break;
        }
    return flow;
}
void print(int x)
{
    if(!x)return;
    printf("%d ",x);
    print(nt[x]);
}
int main()
{
    cin>>n>>m;
    S=n*2+1,T=n*2+2,cnt=1;
    for(int i=1;i<=n;i++)
    {
        add(S,i,1,++cnt);
        add(i,S,0,++cnt);
        add(i+n,T,1,++cnt);
        add(T,i+n,0,++cnt);
    }
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        v+=n;
        add(u,v,inf,++cnt);
        add(v,u,0,++cnt);
    }
    while(init())
        dfs(S,inf);
    for(int i=2;i<=cnt;i+=2)
    {
        int p1=to[i],p2=to[i^1];
        if(p1==S||p1==T||p2==S||p2==T)continue;
        if(w[i^1])nt[to[i^1]]=to[i]-n,r[to[i]-n]=true;
    }
    for(int i=1;i<=n;i++)
        if(!r[i])
        {
            ans++;
            print(i);
            cout<<endl;
        }
    cout<<ans;
}