USACO/fence

分析

　　这道题是要求我们求出一条欧拉路，所以我们要首先判断图中是否有欧拉路。对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；如果超过2个点的度为奇数，那么它就不存在欧拉路了。

　　由于题目中说数据保证至少有1个解，所以一定存在欧拉路了。但是我们还要选一个点作为起点。如果没有点的度为奇数，那么任何一个点都能做起点。如果有2个奇点，那么就只能也这两个点之一为起点，另一个为终点。但是我们要注意，题目要求我们输出的是进行进制转换之后最小的（也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等），所以我们要以最小的点做起点。

　　找出欧拉路的方法就是采用深搜的方式，对于当前的点，把所有点从小到大的搜索，找到和它相连的，找到一个之后删除它们之间的连线，并去搜索新的那个点，如果没有找到点和它相连，那么就把这个点加入输出队列。

　　不过我们这么操作之后，顺序是反着的，输出时反着输出即可。

注意这道题的几个猥琐点…首先,没有跟你说点的序号一定是从1开始的… 例如这组数据:

  1
  10　20

然后…两个点之间可能有不止一条道路…例如:

  78
  1　2
  2　1
  1　2
  2　1
  …(省略N行)

提问与解答

为什么每次取最小的然后逆序就是对的呢，求解答。

---

我在这里提个问题：为什么递归着直接顺序输出时结果 与 存储在输出队列中逆序输出不一样呢？　　 （经过众牛的讨论认为这是由于爆栈的原因，本小菜弱弱的Orz一下：原来输出也会爆栈……）

---

哦，想通了，是这样的：

这个程序每次总是随意挑一条能走的路，走过去。（我知道是按顺序，但是本质上是随意的）尝试考虑下面的图形：

如图，本来应该是E1->E2->E4->E5->E3。 但是由于算法随机选择，有可能走了E1->E2->E3。 中间缺了一个环，于是就要求我们最后把那个环补上。

如果是先输出，后找路的话，结果为V1->V2->V3->V4->V2->V3。这不就不对了嘛！

根本原因是由于程序随机找路，会犯错误，而只有后记录，反输出，才能够给程序一次改过自新的机会啊！

Mr.Phone 16:43 2011年8月23日 (CST)

---

我也有同样的问题，现在很迷茫。

---

那么任何一个点都能做起点。

<---No.Use vertex 1.

<---I haven't install chinese shurufa,wawa!

---

弱弱的问一下为什么递归着直接顺序输出会爆栈呢？？？？？

---

我也遇到了这种情况

procedure search (s:word);
var
  i:word;
begin
  for i:=1 to m do
    if con[s,i]>0 then
    begin
      dec(con[s,i]);
      dec(con[i,s]);
      search(i);
    end;
  inc(j);
  path[j]:=s;
end;

然后倒叙输出，这样写就对

但

procedure search (s:word);
var
  i:word;
begin
  writeln(s);
  for i:=1 to m do
    if con[s,i]>0 then
    begin
      dec(con[s,i]);
      dec(con[i,s]);
      search(i);
    end;
end;

就悲剧了 求条明路 --------------dsqwwe

---

我一开始也遇到了以上问题，经高人指点后有所明白

你可以想想最先执行

 inc(j);
 path[j]:=s;

这段代码的必定是终点，而中间的环的顶点都会进入这个数组，所以没有遗漏，这是正解。

---

有可能在深搜的过程中出现环，所以，可能是在后面的过程中找到当前的值。

---

用弗罗莱（Fleury）算法,时间复杂度o(e*e)

---

这个题最快时间复杂度是Θ(m*(lnm)/(ln2))毕竟这个题要求字典序，所以一定要排序，使每条边的点按顺序排好，排序方法有很多的。 单论欧拉回路最快时间复杂度是Θ（m）.如果是随机图我们用向量存图的话效率最高，因为一般链表存图常数比向量存图大10倍。但是向量存图会退化成Θ(m*m)。如果不是随机图我们应该用双向链表（不能单向链表）来完成这个题，你也可以用map容器做，但是我只能说也很麻烦，时间估计也是Θ(m)，但是插入就比较慢了，而且关于反向边的部分操作可能很难做到Θ(1)。每次找到一条边去走的时候把这条边和他的反向边删了，这样就是Θ（m）了。

一些疑问： 1.如果想时间复杂度达到Θ(m)为什么不能单向链表？ 答：单向链表只能删除这个点后面的元素，无法删除自己（也就是erase_after(it)），如果你存反向边的时候是存的是这个元素前面的那个迭代器的话，由于图比较随机。你这次的删除很可能会使下一次删除的这条边的反向边的前一个链表上的元素不存在，而且会使这些迭代器失效。 2.为什么链表存图常数比向量存图做图时大10倍？ 答：具体原因我也不清楚，但是在大量平台测试的结果都是如此，估计是这种数据结构不利于cpu的计算。你做spfa时会有这种感触的。 3.向量是不是一定比链表快？ 答：虽然做图向量很快，但是链表读入却很快，所以有时会表现出链表更快一些，因为读入很多时候也很耗时。 4.考试若不开O1，O2，库容器不是很慢吗？ 答：首先你要明白库容器的效率就是按照O1的标准做的，你可别拿O0的表现来测试东西（O0连内联都不会展开的，再加上大量的无用的对象构造，所以固然很慢），O1以后就很快了。 若真不开O1，O2,对于向量存图有很好的办法： 就是对一个以后不会再插入或删除元素的vector,例如： std::vector<int> vecc(50，1); int *vec(&vecc.front());//C++11标准规定这种操作在向量不为空时合法，实际上就是为空了也没问题。新标准规定vec.data()==&vec.front() 然后拿vec来当向量操作就行了，例如vec[2]=2就等价于vecc[2]=1.

具体可以看我的C++代码。

--Lgeecn 2013年8月13日 (二) 20:52 (CST)

---

我的思路： 把此题分成两种情况讨论： 欧拉通路：将图分成三个子图：一个存在欧拉回路的图和两个存在欧拉通路的图。从度为奇数的编号最小的点出发，如果走了“歧途”（走到了尽头却还没走完所有边），这个“歧途”则最后再走，于是将其压入栈底，从而一次就能遍历全部边，使算法复杂度为O(e)。 欧拉回路：直接从编号最小的点出发即可一次遍历。 存储：邻接矩阵就够了，记录两点之间几条边，删除边就正反两边数减一即可。 此题如果和遍历点一样dfs则会超时（dfs编写调试了两天，代码100+，此算法参阅了nocow上的代码，仅仅编写调试了一小时，代码70……悲剧……orz大神）感觉我在炒冷饭……

参考代码

c

C++

pascal

引用

[1]

[2]

[3]

[4]