本文主要是介绍HDUOJ 4738 Caocao‘s Bridges 题解 桥 割边 Tarjan，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：HDUOJ 4738 Caocao’s Bridges
题目描述：
给定一个无向图，你可以选择最多删除一条边，删除边的代价是边的边权（特殊地，删除一条边权为
0的边的代价是1），问最小代价使得图不连通。如果无论如何图都是连通的，那么则输出-1。
题解：
题目也就是需要我们求一条桥边，这个桥边所拥有的边权最小。我们只需要求出所有的桥边，然后对边权取一个最小值即可（需要注意边权为
0的边我们要将其变成边权为1的边）。同时需要注意的是，对于一个本身就不连通的图，那么最小的花费是0。
通过Tarjan判断一条u,v之间的边是否是桥，我们只需要判断low[v]>dfn[u]是否成立，不过需要注意的是由于可能存在重边，所以我们在搜索的时候不应该通过反向边更新low[u]但是可以通过重边更新low[u]（重边一定不会是桥）。
代码：HDUOJ4738
这篇关于HDUOJ 4738 Caocao‘s Bridges 题解 桥 割边 Tarjan的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
