※ 引述《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