最小路径覆盖

最小路径覆盖问题：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。

 

我们给这个问题建立一个二分图模型。把所有顶点 i 拆成两个：位于 X 部的结点 ix 和 Y 部结点 iy，可以理解为起点和终点。如果图中存在一条边 i-> j， 则在二分图中加入边 ix-> jy， 设此二分图的最大匹配数为 m，则最小路径覆盖数量为顶点数量 n- m。

 

对于这个结果可以这样理解：

假设原图中都没边，对于 n 个顶点，则需要 n 条路径覆盖，然后我们可以通过对原图加边来减少路径数。加的边是与建立的二分图的匹配是相对应的。比如如果二分图中有匹配 ix->jy ，那么我们在图中加边 i-> j，加的边肯定会构成简单路径，并且不会出现 i-> j， i-> k都有路径或者 i->k, j->k 都有路径的情况，这是由二分图的性质决定，因为二分图中是将原图的点拆成两个，所以匹配中点与原图对应的点最多有两条边与之相连，并且如果有两条边，这两条边一定是与拆开的点在 X 部的与在 Y 部的相连，而不会同时与 X 部或 Y 部的相连。所以当匹配数最大时，路径数就最小，最小值为 n- m。

 

对于有向无环图的顶点可以重复的最小路径覆盖问题也可以转化为标准的最小路径覆盖问题解决。

先用传递闭包将连通性传递建立新图，在新图中求最小路径覆盖。

代码(Poj2594):

#include <stdio.h>

int const N= 550;
int mat[N][N], flag[N<<1], map[N<<1][N<<1], match[N<<1], n, m;

int dfs( int x ){
    for( int y= 1; y<= (n<<1); ++y )
    if( map[x][y] && !flag[y] ){
        flag[y]= 1;
        int t= match[y];
        if( t== -1 || dfs(t) ){
            match[y]= x;
            return 1;
        }
    }
    return 0;
}

int main(){
    while( scanf("%d%d",&n,&m)!= EOF ){
        if( n== 0 && m== 0 ) return 0;
        
        for( int i= 0; i<= n; ++i )
        for( int j= 0; j<= n; ++j ) mat[i][j]= 0;
        
        for( int i= 0; i<= (n<<1); ++i )
        for( int j= 0; j<= (n<<1); ++j ) map[i][j]= 0;
        
        while( m-- ){
            int x, y;
            scanf("%d%d",&x,&y);
            mat[x][y]= 1;
        }
        
        for( int k= 1; k<= n; ++k )
        for( int i= 1; i<= n; ++i )
        for( int j= 1; j<= n; ++j )
        mat[i][j]= mat[i][j]||mat[i][k]&& mat[k][j];
        
        for( int i= 1; i<= n; ++i )
        for( int j= 1; j<= n; ++j )
        if( mat[i][j] ) map[i][j+n]= 1;
        
        for( int i= 0; i<= (n<<1); ++i ) match[i]= -1;
        int ans= 0;
        for( int i= 1; i<= (n<<1); ++i ){
            for( int j= 0; j<= (n<<1); ++j ) flag[j]= 0;
            ans+= dfs(i);
        }
        printf("%d\n", n- ans );
    }
    
    return 0;
}