首页 > 其他分享 >Trick:最小环

Trick:最小环

时间:2023-03-16 09:23:41浏览次数:33  
标签:1x 复杂度 最小 Trick cdots 枚举

求无负环无向图至少具有三个节点的最小简单环,考虑最小的简单环 \(x_1x_2x_3\cdots x_nx_1,n\ge 3\),不妨令 \(x_n=max\{x_i\}\),那么显然有 \(x_1x_2\cdots x_{n-1}\) 是只经过 \([1,x_n)\) 间节点的最短路,因此当 floyd 更新到 \(x_n-1\) 时,枚举 \((u,v)\in[1,x_n)^2\),则有 \(x_nPath(u,v)x_n\) 是一个合法的环,并且总会枚举到该图的最小环。有向图同理,复杂度 \(O(n^3)\)。

又或者可以每次删除一条边跑最短路,复杂度 \(O(m(ShortestPath))\)

标签:1x,复杂度,最小,Trick,cdots,枚举
From: https://www.cnblogs.com/watware-cym/p/17221092.html

相关文章

  • 基于LS最小二乘法的数据拟合matlab仿真
    1.算法描述       最小均方算法,简称LMS算法,是一种最陡下降算法的改进算法,是在维纳滤波理论上运用速下降法后的优化延伸,最早是由Widrow和Hoff提出来的。该算......
  • TZOJ 5788: 最优布线问题 最小生成树
    描述  学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接......
  • 旋转数字的最小数字
    classSolution{public:intfindMin(vector<int>&nums){if(!nums.size())return-1;intn=nums.size()-1;while(n>0&&nums[n]==n......
  • debian安装最小桌面,中文和 浏览器
    debian安装最小桌面,适合vnc使用apt-yupdateapt-yupgrade#安装中文apt-yinstallaptitudeaptitudeinstalllocalesdpkg-reconfigurelocalesnano/etc/default/l......
  • 输入一个数找大于它最小质数!!!
    importjava.util.Scanner;publicclassText2{publicstaticvoidmain(String[]args){Scannerx=newScanner(System.in);inta=x.next......
  • 数组之长度最小的子数组
    1、给定一个含有 n 个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组 [numsl,numsl+1,...,numsr-1,numsr],并返回其......
  • 剑指 Offer 11.旋转数组的最小数字
    题目描述   解法二分查找思路:设i为左界,j为右界,中点为mid;将number[mid]与number[j]进行比较,会出现一下情况:number[mid]<number[j]时,说明number[mid]是最......
  • PAT Basic 1023. 组个最小数
    PATBasic1023.组个最小数1.题目描述:给定数字0-9各若干个。你可以以任意顺序排列这些数字,但必须全部使用。目标是使得最后得到的数尽可能小(注意0不能做首位)。例如......
  • 常见 Trick
    二维凸包的点数在随机情况下是\(O(\logn)\)的。树的高度在随机情况下是\(O(\logn)\)的。要求最大值最小值的时候,有三个方向:min-max容斥,二分,直接求。条件很复杂......
  • 华为OD 最小施肥机能效
    ......