POJ 1422

发表于 更新于 分类于 阅读次数：

   题意不追溯，关于匈牙利算法看：http://my.oschina.net/xuwei8091/blog/126320。 最小路径覆盖等于N-最大匹配

#include #include #include using namespace std;
int T;
int n,m;
int map[200][200];
int vis[200];
int result[200];
bool find(int s)
{
for (int i=1;i<=n;i++)
{
if (map[s][i] && !vis[i])
{
vis[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=s;
return true;
}
}
}
return false;
}
int main()
{
scanf(“%d”,&T);
while (T–){
memset(map,0,sizeof(map));
memset(result,0,sizeof(result));
scanf(“%d%d”,&n,&m);
for (int i=0;i