大意:
奶牛对牛栏有各自的喜好,一个奶牛进一个牛栏,一个牛栏只能放一只奶牛,问最多能放多少奶牛。
分析与实现:
最典型的二分图最大匹配问题。毫无疑问,用匈牙利算法。算法本身很简单:对每个节点,找增广轨。
对每个牛节点做深度优先搜索的过程可以用直观的方式来描述,一头奶牛找牛栏的过程如下:
奶牛观察自己所喜欢的所有牛栏
a) 如果这个牛栏已经换过一次牛了,看下一个
b) 找到一个“新”的牛栏(没换过牛,或者是空的),打上标记。如果这个牛栏没被占用,则搜索成功。
c) 否则,尝试把占用这个牛栏的奶牛赶走,让它去找新的牛栏(递归调用),如果该奶牛报告能找到新地方,则本次搜索成功,确定本奶牛占用本牛栏,并向上一头奶牛报告。
每个奶牛开始找牛栏之前清理上一次留下的标记,重复这个过程,最后请点一下进入牛栏的奶牛数量,就是所得的匹配。
网上流传的代码是递归实现的,不过大多数都是抄过来直接用,以至于没有注意到明显的问题:注意代码22行,几乎所有网上的代码都有这一行代码,其实是错的。这些算法没出问题的原因,是它们将二分图的两部分存放在一个邻接表中,这样,牛的标号和牛栏的标号是不一样的,这一行废代码也就不会带来副作用。不过可见“一大抄”。
重写了递归的代码,并重写了一份非递归实现的代码。非递归实现事实上是一个回溯搜索的过程,不是普通的深度优先搜索,这需要特别注意。
/* ID: blackco3 TASK: stall4 LANG: C++ */ #include <iostream> #include <memory.h> using namespace std; const int _max_group_size_(200) ; struct t_node { int n_adj; t_node *adjs[_max_group_size_] ; } cows[_max_group_size_] , stalls[_max_group_size_] ; int n_cow, n_stall ; t_node *cow_in_stall[_max_group_size_] ; int vis[_max_group_size_] ; #ifdef __recursive__ int find_enpath( t_node *p_cow ) { //vis[ p_cow-cows ]=1 ; for( t_node **pp_stall = p_cow->adjs ; pp_stall != p_cow->adjs + p_cow->n_adj ; pp_stall++ ){ register int stall_no = *pp_stall-stalls ; if( vis[stall_no] ) continue ; vis[stall_no] = 1 ; if( !cow_in_stall[ stall_no ] || find_enpath( cow_in_stall[ stall_no ] ) ) { cow_in_stall[stall_no] = p_cow ; return 1 ; } } return 0 ; } #else int stack[_max_group_size_], stall[_max_group_size_] ; int find_enpath( t_node *p_cow ) { int top=0 ; stack[top]=p_cow-cows, stall[top]=0 ; do { register int cur_cow = stack[top] ; for( ; stall[top] != cows[cur_cow].n_adj ; stall[top]++){ register int stall_no = cows[cur_cow].adjs[ stall[top] ]-stalls ; if( vis[ stall_no ] ) continue ; vis[ stall_no ] = 1 ; if( !cow_in_stall[ stall_no ] ) { while( top >=0 ) { stall_no = cows[ stack[top] ].adjs[ stall[top] ]-stalls ; cow_in_stall[stall_no] = cows + stack[top] ; top-- ; } return 1 ; } stack[++top] = cow_in_stall[ stall_no ]-cows, stall[top]=0 ; break ; } while( top>=0 && cows[stack[top]].n_adj==stall[top] ) top-- ; }while( top>=0 ) ; return 0 ; } #endif int max_match_Hungarian( ) { int n_match=0 ; for( t_node *pc=cows; pc != cows+n_cow; pc++ ){ memset( vis, 0, sizeof(int)*n_stall ); n_match += find_enpath( pc ) ; } return n_match ; } int main() { freopen("stall4.in", "r", stdin); freopen("stall4.out","w",stdout); cin >> n_cow >> n_stall ; for( t_node *pc=cows; pc != cows+n_cow ; pc++ ){ cin >> pc->n_adj ; for( t_node **p_adj=pc->adjs ; p_adj!=pc->adjs+pc->n_adj ; p_adj++ ) { int stall_no ; cin >> stall_no ; *p_adj = stalls + (--stall_no); stalls[ stall_no ].adjs[ stalls[ stall_no ].n_adj++ ] = pc ; } } cout << max_match_Hungarian() << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 877英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1124英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1837郁闷。不小心覆盖了重 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1188英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 960英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1056英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1396英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 766英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 791英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 958英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1198英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 907英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1085英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 766英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1222英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1039英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 921英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1300英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 862英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ... -
USACO Training Section 3.2 Stringsobits
2010-01-18 01:04 983英文原题 中文题译 大意:求至多有L个1的第i个N位二进 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
USACO题目The Clocks解答,包括代码
One of the answer of the USACO training exercises.
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
USACO题目Friday the Thirteenth,包含代码解析
USACO1-5单元AC的代码~ 1 Chapter1 1.1 Section 1.1 1.2 Section 1.2 1.3 Section 1.3 1.4 Section 1.4 1.5 Section 1.5 2 Chapter2 2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 ...
USACO全部译题 USACO Training Program Gateway
[USACO 1.1.4]破碎的项链.cpp
第二行到第 N+1 行: 每行有三个整数,Si, Ei, 和 Ci 第一个星期,农夫约翰随便地让 第一行 两个整数,N (0 ) 和 M
USACO_培训USACO_培训Ride.java-> Gift1.java->
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
usaco历年测试数据