标签:图论-负环

题意给出一个有向图,有边权 $w_i$ 和点权 $s_i$ 。要求找一个环,使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。其中点数 $N\le 1000$ ,边数 $M\le 5000$ 。题解$0/1$ 分数规划。设当前二分值为 $mid$ ,题目即为$$\dfrac{\sum s_i}{\sum w_i} > mid$$$$\sum (s_i-mid\time...
题解 图论-负环
提高+/省选-
题意给一个有向图,如果有负权回路输出-1,否则输出从起点 $S$ 到各个点的最短路长度,如果不连通输出NoPath。其中点数 $N\le 1000$ ,边数 $M\le 100000$ 。题解做法很显然,就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环,求最短路就顺便继续用,然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ,但我又不想删判负环的所以就写了两个。#includ...
题解 图论-最短/最长路 图论-负环
题意定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图,求最小圈的平均值,保留 $8$ 位小数。其中点数 $n\le 3000$ ,边数 $m\le 10000$ 。题解$0/1$ 分数规划,直接二分答案 $mid$ ,然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界,否则增大下界。#include<bits/stdc++.h&...
题解 算法-二分/三分 图论-负环
省选/NOI-