欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - CodeVS1904
题目传送门 - 洛谷2764
题意概括
给出一个有向无环图，现在请你求一些路径，这些路径覆盖且仅覆盖所有的点一次。
现在让你求最少要几条路径。
CodeVS1904 - 只需要输出几条边
洛谷2764 - 先输出路径，再输出几条。（但是截止2017-08-11，还没有SPJ）
题解
话说我这一题一开始在洛谷做，由于没有SPJ，多次爆零，据说在洛谷的那个数据只有网络流可以做？匈牙利挂了（因为没有SPJ）？
首先，我们把题目中的每一个点看成两个点。
对于一个点a, 我们把他看作x（出点，仅连出边）和y（入点，仅连入边）。
然后通过读入的边，构建新的图。
然后我们发现整个图是一个二分图。
那么就可以用匈牙利算法，求出最大匹配总数，然后用总点数减去它，就是答案。
为什么？ 因为你选出的路径中，路径条数 = 总点数 - 选择的边的条数。（这个自己想想为什么吧，不解释）
然后二分图匹配数其实就是选择的边数，那么路径条数 = 总点数 - 选择的边数 = 总点数 - 二分图匹配的边数。
如果用网络流做，可以开一个源点和一个汇点，然后在之前的基础上，链接源点到x类点的边和y类点到汇点的边。洛谷没有SPJ，貌似只能用网络流做。
至于输出路径，我们可以任意确定点，然后向该点的对应点的匹配点和该点匹配点延伸，然后标记掉，找到所有点之后再输出；当然可能会有多条路径，所以这一步做完之后是不够的，我们得不停的找没有被标记的点，直到所有的点都被标记，那么路径就生成完毕了。具体实现可以参见我的第二份代码 - 洛谷2764
至于网络流 -> 可以看这个 -> 传送门
代码 - CodeVS1904
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=*+,M=N*N;
struct Gragh{
int cnt,x[M],y[M],nxt[M],fst[N];
void set(){
cnt=;
memset(fst,,sizeof fst);
}
void add(int a,int b){
cnt++;
x[cnt]=a,y[cnt]=b;
nxt[cnt]=fst[a],fst[a]=cnt;
}
}e;
int n,m;
int match[N],demat[N];
bool vis[N];
bool dfs(int x){
for (int i=e.fst[x];i;i=e.nxt[i])
if (!vis[e.y[i]]){
vis[e.y[i]]=;
if (match[e.y[i]]==-||dfs(match[e.y[i]])){
match[e.y[i]]=x;
return ;
}
}
return ;
}
int q1[N],q2[N],zq1,zq2;
int main(){
scanf("%d%d",&n,&m);
e.set();
for (int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
e.add(x,y+n);
}
int cnt=;
memset(match,-,sizeof match);
for (int i=;i<=n;i++){
memset(vis,,sizeof vis);
if (dfs(i))
cnt++;
}
memset(demat,-,sizeof demat);
for (int i=n+;i<=*n;i++)
if (match[i]!=-)
demat[match[i]]=i;
memset(vis,,sizeof vis);
printf("%d",n-cnt);
return ;
}
代码 - 洛谷2764 - 由于缺少SPJ而WA
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=*+,M=N*N;
struct Gragh{
int cnt,x[M],y[M],nxt[M],fst[N];
void set(){
cnt=;
memset(fst,,sizeof fst);
}
void add(int a,int b){
cnt++;
x[cnt]=a,y[cnt]=b;
nxt[cnt]=fst[a],fst[a]=cnt;
}
}e;
int n,m;
int match[N],demat[N];
bool vis[N];
bool dfs(int x){
for (int i=e.fst[x];i;i=e.nxt[i])
if (!vis[e.y[i]]){
vis[e.y[i]]=;
if (match[e.y[i]]==-||dfs(match[e.y[i]])){
match[e.y[i]]=x;
return ;
}
}
return ;
}
int q1[N],q2[N],zq1,zq2;
int main(){
scanf("%d%d",&n,&m);
e.set();
for (int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
e.add(x,y+n);
}
int cnt=;
memset(match,-,sizeof match);
for (int i=;i<=n;i++){
memset(vis,,sizeof vis);
if (dfs(i))
cnt++;
}
memset(demat,-,sizeof demat);
for (int i=n+;i<=*n;i++)
if (match[i]!=-)
demat[match[i]]=i;
memset(vis,,sizeof vis);
for (int i=;i<=n;i++){
if (vis[i])
continue;
vis[i]=;
zq1=zq2=;
q1[]=q2[]=i;
int x=i;
while (demat[x]!=-)
x=demat[x]-n,q1[++zq1]=x,vis[x]=;
x=i;
while (match[x+n]!=-)
x=match[x+n],q2[++zq2]=x,vis[x]=;
for (int j=zq2;j>=;j--)
printf("%d ",q2[j]);
for (int j=;j<=zq1;j++)
printf("%d ",q1[j]);
puts("");
}
printf("%d",n-cnt);
return ;
}