POJ 2594 最小路径覆盖(点重复)

POJ 2594

二分图性质: 最小路径(点)覆盖(路径不相交) = N - 最大匹配

题意:

• 在有向无环图.求最小路径(点)覆盖(路径相交的点可重复)

思路

• 假设一条路径经过u->p->v,另一条x->p->y.路径相交于点p,于是添加一条x->y或者u->v的边 能够使得2条路径不相交
• 进一步: 将有向图中所有的间接点.通过添加有向边(x,y)变为直接连接的点.那么有路径相交的(点)覆盖 转化成了 无路径相交的(点)覆盖

---

传递闭包的证明及其构造

• 大概意思: 点(事件)a与点b相连,点b与点c相连.通过b来传递关系.那么a与c其实也是相连的
• 通过floyd来一手传递闭包(关系传递). 顺便剪个枝

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 510;
int n,m;
int g[maxn][maxn],match[maxn];
bool vis[maxn];

int dfs(int u) {
    for (int i=1; i<=n; ++i)
        if (g[u][i] && !vis[i]) {
            vis[i] = 1;
            if (match[i]==-1 | dfs(match[i])) {
                match[i] = u;
                return 1;
            }
        }
    return 0;
}

int solve() {
    for (int k=1; k<=n; ++k)
        for (int i=1; i<=n; ++i)
            if (g[i][k]) { //剪枝
                for (int j=1; j<=n; ++j)
                    if (g[i][k]+g[k][j] == 2)
                        g[i][j] = 1;
            }
    int res = 0;
    memset(match,-1,sizeof match);
    for (int i=1; i<=n; ++i) {
        memset(vis,0,sizeof vis);
        if (dfs(i)) ++res;
    }
    return res;
}


int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d%d",&n,&m) && (n+m)) {
        memset(g,0,sizeof g);
        while(m--) {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x][y] = 1;
        }
        printf("%d\n",n-solve());
    }
    return 0;
}