题解：P10951 最优高铁环

GY程袁浩 · 2025-04-11 21:32:12 · 题解

考虑套路 01 分数规划。对于每个作为路线的首尾的车次，当作一个点，对于每条路线首连尾。根据 01 分数规划的套路，二分答案然后建图在图上找正环即可。

建议评蓝。另外这题实际上是不规范的，因为他需要 SPFA 来判负环，数据却不对。为了通过这题，我们需要卡时，具体的，在 SPFA 循环次数过多时，直接认为有正环。

// Problem: P10951 最优高铁环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10951
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
(sigma v)/n>=mid

(sigma v)>=mid*n

(sigma v)-mid*n>=0

(sigma v-mid)>=0
*/

#include <bits/stdc++.h>
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int h[N], ne[N], e[N], w[N], idx, cnt;
double dist[N];
int in[N];
bool st[N];
unordered_map<string, int> ha;
int hav(string x) {
    if (!ha[x]) return ha[x] = ++cnt;
    return ha[x];
}
int va(char g) {
    if (g == 'S')
        return 1000;
    else if (g == 'G')
        return 500;
    else if (g == 'D')
        return 300;
    else if (g == 'T')
        return 200;
    else if (g == 'K')
        return 150;
    return 0;
}
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}
int m;
bool spfa(double mid) {
    queue<int> qq;
    memset(st, 0, sizeof st);
    memset(in, 0, sizeof in);
    upp(i, 1, cnt) {
        dist[i] = 0;
        st[i] = 1;
        qq.push(i);
    }
    int sum = 0;
    while (qq.size()) {
        auto iter = qq.front();
        st[iter] = 0;
        qq.pop();
        for (int i = h[iter]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[iter] + w[i] - mid) {
                dist[j] = dist[iter] + w[i] - mid;
                if (++in[j] > cnt) return 1;
                if (++sum > 100000) return 1;
                if (!st[j]) {
                    st[j] = 1;
                    qq.push(j);
                }
            }
        }
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> m;
    upp(i, 1, m) {
        string str;
        cin >> str;
        int st = -1, ed = -1, c = 0;
        string now = "";
        upp(j, 0, (int)str.size() - 1) {
            if (str[j] == '-') {
                if (st == -1) st = hav(now);
                now = "";
            } else
                now += str[j];
            c += va(str[j]);
        }
        ed = hav(now);
        add(st, ed, c);
    }
    double l = 0, r = 4e9;
    while (r - l > 1e-2) {
        auto mid = (l + r) / 2;
        if (spfa(mid))
            l = mid;
        else
            r = mid;
    }
    if (!spfa(l))
        cout << -1 << endl;
    else
        cout << setprecision(0) << fixed << l << endl;
    return 0;
}