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; }