洛谷 P2764 最小路径覆盖问题

传送门 $\looparrowright$

题目描述

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

输入格式

第一行有 $2$ 个正整数 $n$ 和 $m$ 。$n$ 是给定有向无环图 $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\leqslant n\leqslant 150,1\leqslant m\leqslant 6000$。

分析

设原来的有向无环图为 $G=(V,E)$，$n=|V|$。把 $G$ 中的每个点 $x$ 拆成编号为 $x$ 和 $x+n$ 的两个点。建立一张新的二分图，$1 ~ n$ 作为二分图左部点，$n+1\sim 2n$ 作为二分图右部点，对于原图的每条有向边 $(x,y)$，在二分图的左部点 $x$ 与右部点 $y+n$ 之间连边。最终得到的二分图称为 $G$ 的拆点二分图，记为 $G_2$。
不加证明地给出定理：有向无环图 $G$ 的最小路径点覆盖包含的路径条数，等于 $n$ 减去拆点二分图 $G_2$ 的最大匹配数；最小路径覆盖中的所有边，在拆点二分图 $G_2$ 中构成一组匹配。最小路径覆盖中每条边 $(x,y)$ 的起点 $x$ 与二分图每条匹配边 $(x,y+n)$ 的左部点 $x$ 是一一对应的。
因此，对一个有向无环图，可建立拆点二分图，利用匈牙利算法求最大匹配，并且可以利用 $\mathrm{match}$ 数组输出匹配方案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2764
Date: 7/26/2020 
Description: Hungarian Alogrithm
*******************************************************************/
#include<iostream>
#include<cstring>
using namespace std;
const int N=153;
const int M=6003;
struct E
{
	int to;
	int Next=-1;
}edge[M<<2];
int head[N<<2],tot;
int n,m;
bool vis[N<<2];
int match[N<<2];
void init();
inline void add_edge(int,int);
bool dfs(int);
int Hungarian();
int main()
{
	cin>>n>>m;
	init();
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		//建立拆点二分图
		add_edge(x,y+n);
	}
	cout<<Hungarian()<<endl;
	return 0;
}
void init()
{
	memset(head,-1,sizeof(head));
	tot=0;
	memset(match,-1,sizeof(match));
}
inline void add_edge(int u,int v)
{
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	head[u]=tot;
}
bool dfs(int x)
{
	for(register int i=head[x];~i;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(!vis[y])
		{
			//vis 记录右部节点的访问情况
			vis[y]=1;
			if(match[y]==-1||dfs(match[y]))
			{
				match[y]=x;
				match[x]=y;
				return 1;
			}
		}
	}
	return 0;
}
int Hungarian()
{
	int ans=0;
	int i;
	for(i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++)
	{
		if(!vis[i])	
		{
			//统一输出右部连向的左部点
			int x=i+n;
			do
			{
				x-=n;
				vis[x]=1;
				cout<<x<<' ';
				x=match[x];
			}while(~x);
			cout<<endl;
		}
	}
	return n-ans;//最小路径覆盖
}