二分匹配的Hopcroft-Carp算法

题目：HDU2063 过山车

果然Hopcroft-Carp算法快，用匈牙利算法15ms，而Hopcorft-Carp却0ms。因为匈牙利算法的时间复杂度为O(n*e)，而Hopcroft-Carp算法O(sqrt(n)*e)

本算法适合处理大一点的数据。。。。。。

#include 
#include 
#include 
#include const int N=1005;
const int INF=1<<28;int g[N][N];
int Mx[N];
int My[N];
int dx[N];
int dy[N];
bool used[N];int Nx,Ny,dis;bool searchP()
{dis=INF;int i,v,u;std::queue Q;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));for(i=0;idis) break;for(v=0;vNy? Nx:Ny;while(k--){scanf("%d%d",&u,&v);u--;v--;g[u][v]=1;}int ans=Hungary();printf("%d\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！