二分图匹配（匈牙利算法的DFS实现）
初始化：g[][]两边顶点的划分情况
建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配
g没有边相连则初始化为0
uN是匹配左边的顶点数，vN是匹配右边的顶点数
调用：res=hungary();输出最大匹配数
优点：适用于稠密图，DFS找增广路，实现简洁易于理解
时间复杂度:O(VE)
***************************************************************************/
顶点编号从0开始的
?
/*
HDU 1151*/
#include
#include
#include
#include
using namespace std; /* ************************************************************************** //二分图匹配（匈牙利算法的DFS实现） //初始化：g[][]两边顶点的划分情况 //建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配 //g没有边相连则初始化为0 //uN是匹配左边的顶点数，vN是匹配右边的顶点数 //调用：res=hungary();输出最大匹配数 //优点：适用于稠密图，DFS找增广路，实现简洁易于理解 //时间复杂度:O(VE) //***************************************************************************/ //顶点编号从0开始的 const int MAXN=150; int uN,vN;//u,v数目 int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u)//从左边开始找增广路径 { int v; for(v=0;v
?