匈牙利算法
以下转载自 北大BBS ACM版 第216篇文章~
匈牙利算法，在ftp上“算法整理”看到的
自己写过几次，也看过一些别人实现的
觉得这一段比较简短清晰，容易套用，适合做
模板
个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载
套着做了一下 1043 What's in a name 和 1087 A Plug for Unix 效率也还好
int Bipartite(bool vc [][MAX],int nv1,int nv2) {
int i, j, x, n;
int q[MAX], prev[MAX], qs, qe;
int vm1[MAX], vm2[MAX];
n = 0;
for( i = 0; i < nv1; i++) vm1[i] = -1;
for( i = 0; i < nv2; i++) vm2[i] = -1;
for( i = 0; i < nv1; i++) {
for( j = 0; j < nv2; j++) prev[j] = -2;
qs = qe = 0;
for( j = 0; j < nv2; j++) if( vc[i][j]) {
prev[j] = -1;
q[qe++] = j;
}
while( qs < qe) {
x = q[qs];
if( vm2[x] == -1) break;
qs++;
for( j = 0; j < nv2; j++) if( prev[j] == -2 && vc[vm2[x]][j]) {
prev[j] = x;
q[qe++] = j;
}
}
if( qs == qe) continue;
while( prev[x] > -1) {
vm1[vm2[prev[x]]] = x;
vm2[x] = vm2[prev[x]];
x = prev[x];
}
vm2[x] = i;
vm1[i] = x;
n++;
}
return n;
}
补充(By Cy)
本人感觉看懂2分图似乎不是一件很容易的事情~ 但是有了例程,做起题来,方便多了~ 不 过，最好还是自己能够搞懂~ 这样,如果稍微变换一下~ 改起来也容易.
试着用这个例程 做了一下: ZJU上的 1137 (Girls and Boys) 和 1140(Courses) 都很 容易的过了~ 效率确实不错~ 而且值得注意的是. 这个是一届ACM的2道题. 也就是说: 那次的ACM(Southeastern Europe 2000) 8道中2道用到了 2分图. 以自己的经验来说: 去年的ACM分区,也遇到了2分图的问题. 但是,由于水平不够,没能做出~ 以往在中国的赛 区,2分图的题也出现过~ 值得引起注意~
浙公网安备 33021202002483