POJ 2594 最小路径覆盖 二分匹配

九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/12842699

n个点 m条有向边

下面m条有向边

问至少多少条路径可以把n个点都覆盖( 注意1个单独的点就是一条路径)

显然路径可以合并, 即传递闭包一样,

如： 所有点都在一条单向边上， 那么把所有路径合并就是1条路径 ， 这样只需一条路径就可以覆盖所有点

( 路径可拆可闭)

注意因为用floyd合并了所有路径， 在最后加边时，边数最大为 N*N 条

#include<stdio.h>#include<string.h>#define N 501struct node{int to,nex;}edge[N*N];int head[N], edgenum;void addedge(int u,int v){node E = {v,head[u]};edge[edgenum] = E;head[u] = edgenum++;}int map[N][N];int n,m;int lef[N];bool T[N];int dfs(int u){for(int i = head[u]; i!=-1; i = edge[i].nex){int v = edge[i].to;if(!T[v]){T[v] = true;if(lef[v] == -1 || dfs(lef[v])){lef[v] = u;return 1;}}}return 0;}int solve(){int ans = 0;memset(lef, -1, sizeof(lef));for(int i = 1; i <= n; i++){memset(T,0,sizeof(T));ans += dfs(i);}return ans;}void Input(){memset(map,0,sizeof(map));int u,v;while(m--){scanf("%d %d",&u,&v);map[u][v] = 1;}}void Floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){if(!map[i][k])continue;for(int j=1;j<=n;j++)if(map[k][j]) map[i][j] = 1;}}void Have_map(){memset(head,-1,sizeof(head)); edgenum = 0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(map[i][j])addedge(i,j);}int main(){while(scanf("%d %d",&n,&m), n+m){Input();Floyd();Have_map();printf("%d\n",n - solve());}return 0;}/*8 81 32 33 43 54 65 66 76 8ans:2*/