POJ 2594 Treasure Exploration（最小路径数变形）

题目链接：
POJ 2594 Treasure Exploration
题意：
允许顶点多条路径经过的最小路径数。
分析：
用Floyd算法将所有间接连通点都变为直接连通，再用匈牙利算法求最大匹配，继而得出最小路径数。

#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAX_N=510;
const int MAX_M=5010;int n,m;
int vis[MAX_N],match[MAX_N],edge[MAX_N][MAX_N];inline void Floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(edge[i][k]&&edge[k][j]){edge[i][j]=1;}}}}
}
inline bool dfs(int u)
{for(int i=1;i<=n;i++){if(edge[u][i] && !vis[i]){vis[i]=1;if(match[i]==-1 || dfs(match[i])){match[i]=u;return true;}}}return false;
}inline void solve()
{memset(match,-1,sizeof(match));int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i)) ans++;}printf("%d\n",n-ans);
}int main()
{while(~scanf("%d%d",&n,&m)&&(n||m)){memset(edge,0,sizeof(edge));for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);edge[u][v]=1;}Floyd();solve();}return 0;
}