作者DJWS (...)
看板ACMCLUB
标题Re: Judge 事务杂记
时间Fri Nov 19 09:36:30 2004
※ 引述《JonathanWang (小尹)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 我找到了匈牙利演算法的程式码 :)
: : 也很努力的想看懂他
: : 好奇问一下
: : 有人知道匈牙利算法的时间复杂度是多少吗?
: 有 weight 的呵? 好像是 n^3 还是 n^4 吧
唔? 还有weight的呀?
我找到的这一份code
就纯粹只是将连edge连多一点而已..并没有什麽weight
那这支程式的时间复杂度是多少呢?
int nx,ny,m;
bool g[MAX][MAX],sy[MAX];
int cx[MAX],cy[MAX];
bool path(int x)
{
for (int y=1;y<=ny;y++)
if (g[x][y] && !sy[y])
{
sy[y]=true;
if (!cy[y] || path(cy[y]))
{
cx[x]=y;
cy[y]=x;
return true;
}
}
return false;
}
int MaximumMatch()
{
memset(cx,0,sizeof(cx));
memset(cy,0,sizeof(cy));
int ans = 0;
for (int x=1;x<=nx;x++)
if (!cx[x])
{
memset(sy,0,sizeof(sy));
if (path(x))
ans++;
}
return ans;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.122.76.208