题目链接
Treasure Exploration POJ - 2594
题意
给定一个有向无环图，求用最少的可以相交的简单路径去覆盖所有结点。
分析
最小路径覆盖是用最少的不相交的简单路径去覆盖有向无环图的所有结点，而这里是可以相交。所有需要简单地变形一下，用floyed去传递闭包，增加一些边使得两条相交路径的所有结点可以用两条不相交路径的所有结点表示。即如果有边（i，j）和（j，k）就增加一条边（i，k）。
代码
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;const int maxn=550;
int from[maxn],vis[maxn],n;
//vector<int> g[maxn];
int w[maxn][maxn];bool Find(int u)
{for(int i=1; i<=n; i++)if(w[u][i]){int v=i;if(!vis[v]){vis[v]=1;if(from[v]==-1 || Find(from[v])){from[v]=u;return true;}}}return false;
}
void solve()
{int ans=0;memset(from,-1,sizeof(from));for(int i=1; i<=n; i++){memset(vis,0,sizeof(vis));if(Find(i))ans++;}printf("%d\n",n-ans);
}
void floyd() // 求图的闭包
{for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){if(w[i][k] == 1){for(int j = 1; j <= n; j++){if(w[k][j] == 1)w[i][j] = 1;}}}}
}
int main()
{int m;while(scanf("%d%d",&n,&m)){if(n==0 && m==0)break;memset(w,0,sizeof(w));while(m--){int u,v;scanf("%d%d",&u,&v);w[u][v]=1;}floyd();solve();}return 0;
}
参考博客
模板总结——二分图最大匹配