本文主要是介绍匈牙利算法模板及解释,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
模板题:usaco The Perfect Stall完美的牛栏
每只牛有几个它喜欢的牛栏,求最多能使多少头牛到它喜欢的牛栏里(一个牛栏只能有一只牛在里面)
假设有4只牛,4个牛栏。
牛1喜欢1、2
牛2喜欢2、3
牛3喜欢2
牛4喜欢1、4
开始匹配!
从牛1开始。牛1发现1没牛,就进了1。到牛2,牛2发现2每牛,就进了。到牛3,牛3发现2居然被占了,就把牛2赶出来,牛2发现3没牛,就到了3,牛3也就住进了2。
最后到牛4,1居然被占了,把牛1赶出来,牛1到2……过了好一会,发现如果牛4住进了1,牛3就住不到2,牛2!@##¥%#¥%,牛1回到了1,对牛4说滚。牛4接着找,找到了4,没牛!住进去,皆大欢喜!
代码:
bool dg(int x)
{if (bz[x]==st) return 0;bz[x]=st;for(int i=last[x];i;i=next[i]){int y=to[i];if (b[y]==0 || dg(b[y])){b[y]=x;return 1;}}return 0;
}
int main()
{for(st=1;st<=n;st++) if(dg(st)) ans++;
}
这篇关于匈牙利算法模板及解释的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!