[ACM] POJ 2594 求有向图(允许路径重叠的)最小路径覆盖, Floyd + 匈牙利算法

111 Replies

大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配呢

而

最小覆盖数 == 节点数 – 最大匹配数

为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读： Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明

求二分图最大匹配用匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可

至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.

怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法

Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:

1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:

[cpp]

#include <stdio.h>
#include <string.h>

void floydMap(bool a[][501],bool A[][501],int N) {
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
a[i][j]=A[i][j];

for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++) {
if(i==j || a[i][j])
continue;
if(a[i][k] && a[k][j])
a[i][j]=true;
}
return;
}

bool orz(bool a[][501],int N,int x,bool visited[501],int yRefer[501]) {
for(int y=1;y<=N;y++) {
if(visited[y] || !a[x][y])
continue;

visited[y]=true;
if(yRefer[y]==-1 || orz(a,N,yRefer[y],visited,yRefer) ) {
yRefer[y]=x;
return true;
}
}
return false;
}

int maxMatch(bool a[][501],int N) {
int yRefer[501];
memset(yRefer,0xff,sizeof(yRefer));

bool visited[501];
int result=0;
for(int i=1;i<=N;i++) {
memset(visited,0x00,sizeof(visited));
if(orz(a,N,i,visited,yRefer))
result++;
}

return result;
}

int main() {
while(1) {
int N,M;
scanf("%d%d",&N,&M);
if(!N)
break;

bool MAP[501][501];
memset(MAP,0x00,sizeof(MAP));
for(int i=0;i<M;i++) {
int from,to;
scanf("%d%d",&from,&to);
MAP[from][to]=true;
}

bool fm[501][501];
floydMap(fm,MAP,N);

int m;
m=maxMatch(fm,N);

printf("%d\n",N-m);
}
return 0;
}
[/cpp]

111 thoughts on “[ACM] POJ 2594 求有向图(允许路径重叠的)最小路径覆盖, Floyd + 匈牙利算法”

Leave a Reply

Your email address will not be published. Required fields are marked *