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

#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 行开始,每行输出一条路径。
文件的最后一行是最少路径数。

样例

样例输入

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 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 ;
}

最小路径覆盖

上一篇:AO创建IFeature的两种方法


下一篇:PyQt5应用与实践