luogu/solutions/P3199.md

P3199 最小圈

思路：找到最小圈相当于找到最小环。

只须二分答案环的平均值的最小值 $mid$，并把每条边均减去 $mid$，使用 SPFA 判断负环即可。

调试记录：

• 二分范围错误
  • 因为存在负边权，二分范围应该为 -10^7 到 10^7
• SPFA 判负环逻辑错误
  • SPFA 判断负环用的是单个路径的长度 > n 而非访问的点个数 > n
• 初始入队点错误
  • 存在圈且有一个点能到达其他所有点，不一定是点 1
• 入队条件错误
  • SPFA 入队的条件是未在队列中且进行了松弛操作
• 队列长度不足
  • 一个点可能多次入队，队列长度应该为 n \times m

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, double>> fri[3005];
int q[30000005];
double d[3005];
bool in[3005];
int cnt[3005];
int ql = 1, qr = 0;
bool check(double minus)
{
    ql = 1, qr = 0;
    memset(d, 0, sizeof d);
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i)
    {
        q[++qr] = i;
        in[i] = 1;
    }
    while (qr >= ql)
    {
        int now = q[ql++];
        in[now] = 0;
        for (pair<int, double> to : fri[now])
        {
            if (d[now] + to.second - minus < d[to.first])
            {
                d[to.first] = d[now] + to.second - minus, cnt[to.first]++;
                if (!in[to.first])
                    q[++qr] = to.first, in[to.first] = 1;
            }
            if (cnt[to.first] > n)
                return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; ++i)
    {
        double w;
        scanf("%d%d%lf", &u, &v, &w);
        fri[u].push_back({v, w});
    }
    double l = -1e7, r = 1e7;
    while (r - l > 1e-9)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%.8lf\n", l);
    return 0;
}