P2764 最小路径覆盖问题
问题描述：
给定有向图\(G=(V,E)\)。设\(P\) 是\(G\) 的一个简单路（顶点不相交）的集合。如果\(V\) 中每个顶点恰好在\(P\) 的一条路上，则称\(P\)是\(G\) 的一个路径覆盖。\(P\) 中路径可以从\(V\) 的任何一个顶点开始，长度也是任意的，特别地，可以为\(0\)。\(G\) 的最小路径覆盖是\(G\)的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图\(G\) 的最小路径覆盖。
提示：设\(V={1,2,.... ,n}\),构造网络\(G_1=(V_1,E_1)\)
如下：
\(V_1=\{x_1,x_2,...,x_n\}\cup\{y_1,y_2,...y_n\}\)
\(E_1=\{(x_0,x_i):i\in V\}\cup\{(y_0,y_i):i\in E \}\cup\{(x_i,y_j):(i,j)\in E\}\)
即每条边的容量均为1。求网络\(G_1\)最大流。
输入输出格式
输入格式：
件第1 行有2个正整数\(n\)和\(m\)。\(n\)是给定有向无环图\(G\) 的顶点数，\(m\)是\(G\) 的边数。接下来的\(m\)行，每行有\(2\) 个正整数\(i\)和\(j\)，表示一条有向边\((i,j)\)。
输出格式：
从第1 行开始，每行输出一条路径。文件的最后一行是最少路径数。
说明
\(1<=n<=150,1<=m<=6000\)
由@zhouyonglong提供SPJ
其实提示说的很清楚了。
这里用我自己的感性语言解释一下。
描述：将图中每个点拆成两个，分成两个图。把连原来的边连上。跑二分图匹配，最小路径数=总点数-最大匹配数。
解释：
不难发现，路径数+路径集合中边的数量=总点数。
总点数不变，我们就可以转化到求最大的边的数量。
而对于原图中的每一个点\(i\),都可以分成以下四中情况。
为了使边的数量尽量大，我们应该多令情况(3)出现。
而这几种情况中又一个点最多戳某一个点屁股，也只能被最多被一个戳。
那么， 匹配？
再看看我们跑的二分图是什么，是不是很明了~
CODE:
#include <cstdio>
#include <cstring>
const int N=160;
int n,m;
struct edge
{
int to,next;
}g[N*N];
int head[N],cnt=0;
void add(int u,int v)
{
g[++cnt].to=v;
g[cnt].next=head[u];
head[u]=cnt;
}
int used[N],match[N];
bool m_find(int u)
{
for(int i=head[u];i;i=g[i].next)
{
int v=g[i].to;
if(!used[v])
{
used[v]=1;
if(!match[v]||m_find(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
}
void dfs(int now)
{
if(!match[now]) {printf("%d ",now);return;}
dfs(match[now]); printf("%d ",now);
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
int ans=0;
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
if(m_find(i)) ans++;
}
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)
used[match[i]]=1;
for(int i=1;i<=n;i++)
if(!used[i])
{dfs(i);printf("\n");}
printf("%d\n",n-ans);
return 0;
}2018.5.6