POJ1422 最小路径覆盖入门

13-09-07 来源：[db:作者]

收藏我要投稿

题意：DAG求最小路径覆盖。

注意：二分匹配只试用于求DAG的最小路径覆盖，有环就不行，具体可以理解证明。

对n个点进行拆点，分成左右两排点，对于边<u, v> 建 <u', v''> 。

然后最小路径覆盖 == 总点数n - 最大匹配。

简单的证明：每匹配一对<u，v>就说明u和v在同一条路径上，拿路径数就少1。

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <vector>  
using namespace std;  
const int maxn = 130;  
vector <int> edge[maxn];  
int n, m;  
int pre[maxn];  
bool vis[maxn];  
bool dfs(int u) {  
    for(int i = 0; i < (int) edge[u].size(); i++) {  
        int v = edge[u][i];  
        if(vis[v]) continue;  
        vis[v] = 1;  
        if(pre[v] == -1 || dfs(pre[v])) {  
            pre[v] = u;  
            return 1;  
        }  
    }  
    return 0;  
}  
int main() {  
    int i, cas;  
    scanf("%d", &cas);  
    while(cas--) {  
        scanf("%d%d", &n, &m);  
        int x, y;  
        for(i = 1; i <= n; i++)  
            edge[i].clear();  
        while(m--) {  
            scanf("%d%d", &x, &y);  
            edge[x].push_back(y);  
        }  
        memset(pre, -1, sizeof(pre));  
        int cnt = 0;  
        for(i = 1; i <= n; i++) {  
            memset(vis, 0, sizeof(vis));  
            cnt += dfs(i);  
        }  
        printf("%d\n", n-cnt);  
    }  
    return 0;  
}

点击复制链接与好友分享!回本站首页