LibreOJ #6002. 「网络流 24 题」最小路径覆盖

2022-02-12 00:31:01

#6002. 「网络流 24 题」最小路径覆盖

内存限制：256 MiB时间限制：1000 ms标准输入输出

题目类型：传统评测方式：Special Judge

上传者：匿名

题目描述

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

设计一个有效算法求一个有向无环图 G GG 的最小路径覆盖。

输入格式

第 1 11 行有 2 22 个正整数 n nn 和 m mm。n nn 是给定有向无环图 G GG 的顶点数，m mm 是 G GG 的边数。
接下来的 m mm 行，每行有 2 22 个正整数 u uu 和 v vv，表示一条有向边 (i,j) (i, j)(i,j)。

输出格式

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

样例

样例输入

样例输出

1 4 7 10 11

2 5 8

3 6 9

3

数据范围与提示

1≤n≤200,1≤m≤6000 1 \leq n \leq 200, 1 \leq m \leq 60001≤n≤200,1≤m≤6000

题目链接：https://loj.ac/problem/6002

题意：输出一个有向图的点不重复的最小路径覆盖。

思路：点不重复的最小路径覆盖。最初始每个点都最为自己一个独立的路径，如果有一个匹配，那么路径-1，所以最小路径覆盖，点不重复的情况就是求最大匹配。

点可重复的最小路径覆盖也是使用匹配，只不过，需要增加一些边，如果u可以到达匹配，则增加<u,v>，这样就会跳过一些中间点。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<queue>

#include<stack>

#include<map>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int maxn=,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;

const ll INF=1e18+;

int n,m;

vector<int>G[maxn];

bool used[maxn];

int cx[maxn],cy[maxn];

bool vis[maxn];

void pprintf(int u)

{

    vis[u]=true;

    if(cx[u]<)

    {

        printf("\n");

        return ;

    }

    printf(" %d",cx[u]);

    pprintf(cx[u]);

}

bool dfs(int u)

{

    for(int i=; i<G[u].size(); i++)

    {

        int v=G[u][i];

        if(used[v]) continue;

        used[v]=true;

        if(cy[v]<||dfs(cy[v]))

        {

            cy[v]=u,cx[u]=v;

            return true;

        }

    }

    return false;

}

int solve()

{

    int res=;

    memset(cy,-,sizeof(cy));

    memset(cx,-,sizeof(cx));

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

    {

        memset(used,false,sizeof(used));

        res+=dfs(i);

    }

    memset(vis,false,sizeof(vis));

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

    {

        if(!vis[i])

        {

            printf("%d",i);

            pprintf(i);

        }

    }

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

}

int main()

{

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

    int u,v;

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

    {

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

        G[u].push_back(v);

    }

    solve();

    return ;

}

最小路径覆盖

码农公寓