英文原题
中文题译
经典的求欧拉路径:给定最多两个奇数度顶点的连通图(保证有欧拉回路),要求出欧拉路径使得每条边均访问到且只访问一次。附加条件:在所有可能欧拉回路中求按访问的节点序号的字典序最小的一个。
求欧拉回路最快的线性时间算法是这样的:从任意一个节点出发,每访问一个节点,就将其入栈,并删除所访问的边,如果到达一个没有边的顶点,则将栈顶元素出栈并输出之。
要在常数时间内删除边,邻接表中就不能存邻接节点,而需存对边的引用(可以是指针,或者是索引),这里用的是指针。从而在一个顶点将某边删除之后另一顶点可常数时间判断出来。
由欧拉回路算法求欧拉路径,只需从两个奇数度顶点之一出发即可,注意判断条件的变更。
本题的第二个限制,要求输出字典序最小的,这样在建立邻接表时顶点要排序,同时,删除边时不能简单的从最后挪一个边到相应位置来。一个最简单的方法就是每次按顺序访问邻接表找第一个未被删除的边。不过这样增加复杂度,更简单合理的方式是挪动邻接表的初始位置。(一般情况下,我们用adj[],n_adj表示邻接表,而这里用p_adj_head,p_adj_tail更为合理。)
可以考虑一下,如果要求按边出现顺序的字典序输出,该如何。
中文题译
经典的求欧拉路径:给定最多两个奇数度顶点的连通图(保证有欧拉回路),要求出欧拉路径使得每条边均访问到且只访问一次。附加条件:在所有可能欧拉回路中求按访问的节点序号的字典序最小的一个。
求欧拉回路最快的线性时间算法是这样的:从任意一个节点出发,每访问一个节点,就将其入栈,并删除所访问的边,如果到达一个没有边的顶点,则将栈顶元素出栈并输出之。
要在常数时间内删除边,邻接表中就不能存邻接节点,而需存对边的引用(可以是指针,或者是索引),这里用的是指针。从而在一个顶点将某边删除之后另一顶点可常数时间判断出来。
由欧拉回路算法求欧拉路径,只需从两个奇数度顶点之一出发即可,注意判断条件的变更。
本题的第二个限制,要求输出字典序最小的,这样在建立邻接表时顶点要排序,同时,删除边时不能简单的从最后挪一个边到相应位置来。一个最简单的方法就是每次按顺序访问邻接表找第一个未被删除的边。不过这样增加复杂度,更简单合理的方式是挪动邻接表的初始位置。(一般情况下,我们用adj[],n_adj表示邻接表,而这里用p_adj_head,p_adj_tail更为合理。)
可以考虑一下,如果要求按边出现顺序的字典序输出,该如何。
/* ID: blackco3 TASK: fence LANG: C++ */ #include <iostream> #include <algorithm> #include <memory.h> using namespace std; const int _n_node_(500), _max_edge_(1024) ; struct t_edge { int v1, v2 ; int used ; } edge_pool[_max_edge_], *p_edge_pool[_max_edge_<<1]; bool edge_comp( t_edge const &pe1, t_edge const &pe2 ){ return pe1.v1==pe2.v1 ? pe1.v2<pe2.v2 : pe1.v1<pe2.v1 ; } struct t_node { int n_adj ; t_edge **adj ; } nodes[_n_node_] ; int n_edge ; int tour_stk[_max_edge_+2], top; int tour( int v ){ while(true){ t_edge **ppe_head=nodes[v].adj, **ppe_tail=ppe_head+nodes[v].n_adj ; while( ppe_head != ppe_tail && (*ppe_head)->used ) ppe_head++ ; node[v].adj=ppe_head, node[v].n_adj=ppe_tail-ppe_head ; if( ppe_tail==ppe_head ) break ; tour_stk[top++]=v ; (*ppe_head)->used=1; v=(*ppe_head)->v1==v? ((*ppe_head)->v2):((*ppe_head)->v1); } return v ; } int main() { freopen("fence.in", "r", stdin); freopen("fence.out", "w", stdout); int n_edge ; cin >> n_edge; memset( nodes, 0, sizeof(nodes)); for( t_edge *p_edge=edge_pool; p_edge!=edge_pool+n_edge; p_edge++ ){ int v1, v2, tmp ; cin >> v1 >> v2 , tmp=--v1, --v2 ; if( v1>v2 ) v1=v2 , v2=tmp ; p_edge->v1=v1, p_edge->v2=v2, p_edge->used = 0 ; nodes[v1].n_adj++, nodes[v2].n_adj++ ; } t_edge **pp_edge =p_edge_pool; int start_node=-1 , end_node=-1 ; for( int i=0; i<_n_node_; i++ ){ nodes[i].adj = pp_edge , pp_edge += nodes[i].n_adj; if( nodes[i].n_adj&1 ) { if( start_node==-1 ) start_node = i ; else end_node = i ; } nodes[i].n_adj = 0 ; } start_node = start_node==-1 ? 0 : start_node ; sort( edge_pool, edge_pool+n_edge, edge_comp) ; for( t_edge *p_edge=edge_pool; p_edge!=edge_pool+n_edge; p_edge++ ){ int v1=p_edge->v1, v2=p_edge->v2 ; nodes[v1].adj[ nodes[v1].n_adj++ ] = p_edge ; nodes[v2].adj[ nodes[v2].n_adj++ ] = p_edge ; } int trace[_max_edge_+2], trace_size=0, v=start_node; top = 0 ; do { tour(v) ; if( !top ) break ; v = tour_stk[--top]; trace[trace_size++] = v ; } while ( true ) ; for( int i=trace_size-1; i>=0; i-- ) cout << trace[i]+1 << endl ; if( end_node!=-1 ) cout << end_node+1 << endl ; else cout << start_node+1 << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 884英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1133英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1849郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1645英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 968英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1065英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1404英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 771英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 798英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 971英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 916英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1093英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 772英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1232英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1046英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 930英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1307英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 868英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ... -
USACO Training Section 3.2 Stringsobits
2010-01-18 01:04 990英文原题 中文题译 大意:求至多有L个1的第i个N位二进 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
One of the answer of the USACO training exercises.
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 Chapter5 5.1 Section 5.1 5.2 Section 5.2 5.3 Section 5.3 5.4 Section 5.4 5.5 Section 5.5
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO题目The Clocks解答,包括代码
第一行 优惠商品的种类数(0 ) 第二行..第 s+1 行 每一行都用几个整数来表示一种优惠方式 第一个整数 n 第一行: 两个用空格隔开的
P8898 [USACO22DEC] Feeding the Cows B 题解.docx
USACO training 教程翻译合集(清晰明确)
USACO题目Friday the Thirteenth,包含代码解析
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看