[JZOJ4735]最小圈

Problem

对于一张有向图,要你求图中最小圈的平均值最小是多少,即若一个圈经过k个节点,那么一个圈的平均值为圈上k条边权的和除以k,现要求其中的最小值
输出一行一个数,表示最小圈的值。你的答案被视为正确当且仅当与标准答案的绝对误差不超过1e-5
\(n \leq 3000, m \leq 10000, |W_{i,j}|\leq 10^5 , W_{i,j}\)表示边权,是实数
继续阅读 [JZOJ4735]最小圈

0

可行性遍历问题简介之Hamilton回路

可行遍历问题是一个很实际的问题:按一定顺序走遍图的所有顶点或者所有边。具体来说可以分为如下四个问题:

  • Hamilton回路问题 是否可以从某点出发顺着边走,每个点恰好走一次以后回到出发点?
  • Euler回路问题 是否可以从某点出发顺着边走,每条边恰好走一次以后回到出发点?
  • 旅行商问题(ISP) 如果每个边上的权值不同,那么在所有Hamilton回路中求出权值和最小的那一条.
  • 中国邮递员问题 如果不存在Euler回路,怎样才能在每条边至少走过一次后回到出发点,并使回路上权值和尽量小?

继续阅读 可行性遍历问题简介之Hamilton回路

0