为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/fence6
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .1中的OI题目Fence Loops的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 做法一
求无向图中的最小环。
算法很简单，就是做m遍dijkstra——每次找到一条边，拿掉，求这条边两个顶点之间的最短路，那么如果这两点间存在最短路，则这条路径与原来的边就构成了一个环。这样所有环中最小的一个就是答案。
问题是题目给出的是边连通的信息而非点连通。也就是说我们得到的信息无法按照常规的方法（邻接矩阵，邻接表）来构图。这里就需要一个转化。由于我想不到什么好的算法，所以就用了一个复杂度为O(n^2)的转化。首先将每条边的两个顶点都看作单独的点（也就是说假设所有边都不连通，为了方便，可以分别设第i条边的两个顶点编号为i*2-1和i*2），然后对于两条连通的边，将连通这两条边的点并在一起。具体做法就是将其中一个点的连通情况全部赋给另一个点，并修改图中其他与该点连通的点信息使得合并成立。这里我借助了并查集，使得每次查找的时间都近似为常数，所以总的时间复杂度就是O(n^2)。其中n是合并后总的点的个数
经过上述转化以后，再用m遍dijkstra，总的算法时间复杂度就是O(mn^2)。
[编辑] 做法二
这道题给的数据是边之间的关系,首先想到的是构图,然后套经典的最短路做.但是这道题的数据输入会使按点构图很麻烦,其实这道题搜索即可,而且加剪枝后很快.由v条边开始搜索在它b方向的边,重复这个过程,直到回到v而且是由a方向回到的,为了判断环可以加个判重,一个剪枝:对于路径长度大于已知最小环的可剪.
[编辑] 做法三
一种比较诡异的方法。就是把边变成“点”。在把“边”的长度设定为边两端的“点”（既原来的边）的长度的和。
用由floyd算法改进的求最小环的算法求最小环。注意的是枚举“点”时，注意“点”连接的两“点”要是分别连接到该“点”代表的边的两个端点。
这个复杂度为O(n^3)。超级快…...
证明略……有兴趣的自己想一下
参考程序:Pascal程序代码
这个做法和我的相似。我补充一下。把篱笆看成是图的顶点，在建图的时候将每一条边的权值赋为它与相邻篱笆的长度和（也就是说每个顶点引出n1s+n2s条边）。
用floyed求最小环的方法求出长度，除以2就是结果。
yuhc
(这个方法是错误的，还是无法避免篱笆交于一点的情况)
话说这是个很纠结的办法……我也是一开始就想的这种方法……但是发现了它很难处理的一个情况—————就是几个篱笆交于一点。
解决办法就是：在求最小环的时候，拿邻接表（边表也可）存储下两端的篱笆，然后分别枚举两端的篱笆，就可以解决这个问题了！
另外本人力挺这种做法！
————SKYWALKER
与此方法类似，构图时I建立2*I和2*I-1两个点，然后将相连的点幷查集，最后套用经典的最小环求法
最初那种直接把点看成边的方法不正确！ 如样例中如果把相连的边变成点后都连上一条边，那么就会把一前不是环的路径变成环，造成错误答案： 如： 样例2,3,8三边不成环，但是当作点连接后就是环了，结果为10，错误！
是啊，卡了好久T_T！！！
其实是可以的 出现LS的情况其实是没有体现题目中数据的方向性 我们把与他左端相连的开个邻接表 右端相连的开个邻接表
这么着就可以避免了
什么边点互化，我弄了好久都没过。
[编辑] 做法四
仍然是求最小环，先将边邻接矩阵转为点邻接矩阵，再dfs求出所有环。
可以证明时间复杂度为O(n^3)，所以能快速AC
还是DFS好 代码也简单
[编辑] 做法五
啥剪枝都不用,直接按边暴力DFS- -唯一需要小心的是找下一条边的时候要注意在另一侧.
[编辑] 做法六
二分答案，也是秒杀ac
哪位能解释一下二分的具体做法？我想不到诶…
回LS，就是迭代加深
[编辑] 做法七
做法三做些改变之后的方法，更加易懂
给交点编号，就使其可以像正常图一样求最小环
用的floyd求最小环
[编辑] 做法八
不用把栅栏当作整体来看，题目没有那么复杂。如果你把栅栏的两端当作两个点，而栅栏当作连接它们的边或路径的话，你会发现，这其实就是一个最短路的问题。但并不是裸的，操作的时候要注意下面几点：
1、题目里要求的是最短的环，转化之后就是求彼此距离最短的在同一栅栏两端的点
2、两段栅栏相接处在题目中是同一个点，但在程序中你可以把它当作分开的点，之间的距离为0，方便做最段路
3、直接用FLOYD做是不行的。对此我已经有了失败的经验。正确的做法是一对一对顶点求，然后不断更新最小值，每次求之前应该把栅栏上的值赋为无穷大，然后把求出来的最短路值加上栅栏上的值、就是这对顶点间的最小环
PS：这样做的复杂度很可观、当中的最短路用SPFA做的话可以在0.00秒AC全部数据
OVER ——H`
[编辑] 做法九
Executing...
Test 1: TEST OK [0.003 secs, 3836 KB] Test 2: TEST OK [0.005 secs, 3836 KB] Test 3: TEST OK [0.008 secs, 3836 KB] Test 4: TEST OK [0.008 secs, 3836 KB] Test 5: TEST OK [0.008 secs, 3836 KB] Test 6: TEST OK [0.008 secs, 3836 KB] Test 7: TEST OK [0.005 secs, 3836 KB] Test 8: TEST OK [0.005 secs, 3836 KB] Test 9: TEST OK [0.003 secs, 3836 KB]
All tests OK.
我自己想到非常诡异的算法！时间复杂度O(n^2)!!!!
1. 以篱笆为边构图
2. prim最小生成树生成一棵树
记下sum[i][j]表示生成树中i点到j点的距离 fa[i]表示i节点在生成树中的父亲编号 则 设i为当前遍历到的节点则
{
sum[i][k]=sum[k][i]=sum[fa[i]][k]+val[i][fa[i]];
}
3. 枚举每一条非生成树中的边 此时它连接的两个在生成树中的顶点之间的路径和它将形成一个环（类似于次小生成树） 然后找最小环就可以了！！！！ 快得飞起类！！！好简单好好写的类！！！代码超级短类！！！不用跑最短路了类！！！觉得好的点个赞类！！！好算法求不删类！！！ --- by LYH
[编辑] Problem?
Is there anyone who's ever said the fence is straight? If not, simple minial-circle might return edges that enclosed more than one pasture. like this:
- fence1 / \ fence2,3 --- fence4 / \ fence4 ------fence5 \____/fence 6,7,8
