网络流24题 第三题 - CodeVS1904 洛谷2764 最小路径覆盖问题 有向无环图最小路径覆盖 最大流 二分图匹配 匈牙利算法

欢迎访问~原文出处——博客园-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 ;
}
上一篇:BZOJ1059 [ZJOI2007]矩阵游戏 二分图匹配 匈牙利算法


下一篇:与焊接厂交流——从生产角度出发的PCB设计心得