题面

幻影国建成了当今世界上最先进的高铁，该国高铁分为以下几类：

S—高速光子动力列车—时速1000km/h
G—高速动车—时速500km/h
D—动车组—时速300km/h
T—特快—时速200km/h
K—快速—时速150km/h

该国列车车次标号由上述字母开头，后面跟着一个正整数(<=1000)构成。

由于该国地形起伏不平，各地铁路的适宜运行速度不同。

因此该国的每一条行车路线都由K列车次构成。

例如：K=5的一条路线为：T120-D135-S1-G12-K856。

当某一条路线的末尾车次与另一条路线的开头车次相同时，这两条路线可以连接起来变为一条更长的行车路线。

显然若干条路线连接起来有可能构成一个环。

若有3条行车路线分别为:

x1-x2-x3
x3-x4
x4-x5-x1

x1~x5车次的速度分别为v1~v5

定义高铁环的值为(环上各条行车路线速度和)的平均值，即：

[(v1+v2+v3)+(v3+v4)+(v4+v5+v1)]/3.

所有高铁环的值的最大值称为最优高铁环的值。

给出M条行车路线，求最优高铁环的值。

输入格式

第一行为行车路线条数M。

接下来M行每行一条行车路线，由若干车次构成，各车次之间用’-‘号隔开，车次的标号方式如上所述。

数据保证输入的合法性。

输出格式

输出最优高铁环的值，四舍五入到最接近的整数。

若不存在这样的环，输出-1.

数据范围

0<M≤50000,
每条行车路线车次个数不超过20，数据保证结果不超过231−1。

输入样例：

3
T120-D135-S1
S1-G12
G12-K856-T120

输出样例：

1283

题解

这题主要难在输入数据的处理, 哈希map,

然后就是01规划,

还有个坑, 普通判负环是要提前知道当前这个图的最大深度的, 然而我们并不知道

只能dfs判负环, 复杂度就不好说了, 玄学(一个点再一次二分判断可能 dfs多次)

最坏 n*n, 然而肯定达不到 ?

代码

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 50000 + 5, p = 13331;
const db eps = 1e-2;

int n, m, _, k;
int h[N << 1], ne[N], to[N], co[N], tot;
unordered_map<ull, int> st;
int f[N << 1], dep[N << 1];
double dis[N << 1];
bool v[N << 1];

void add(int u, int v, int c) {
    ne[++tot] = h[u]; to[h[u] = tot] = v; co[tot] = c;
}

int get(int x) {
    switch (x) {
    case 'S': return 1000;
    case 'G': return 500;
    case 'D': return 300;
    case 'T': return 200;
    default: return 150;
    }
}

bool dfs(int x, double mid) {
    v[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = to[i]; double c = mid - co[i];
        if (dis[y] > dis[x] + c) {
            dis[y] = dis[x] + c;
            if (v[y] || dfs(y, mid)) return 1;
        }
    }
    v[x] = 0;
    return 0;
}

bool check(double mid) {
    rep (i, 1, n) dis[i] = 0x3f3f3f3f, v[i] = 0;
    rep (i, 1, n)
        if(dfs(i, mid)) return 1;
    return 0;
}

int main() {
    IOS; cin >> m;
    rep(i, 1, m) {
        string s; cin >> s;
        ull u = 0, v = 0; int co = 0;
        for (char& c : s)
            if (c == '-') u = (u ? u : v), v = 0;
            else co += (v ? 0 : get(c)), v = v * p + c;

        if (!st.count(u)) st[u] = st.size() + 1;
        if (!st.count(v)) st[v] = st.size() + 1;
        add(st[u], st[v], co);
    } n = st.size();

    double l = 0, r = 2147483648, ans = -1;
    while (r - l > eps) {
        double mid = (r + l) / 2;
        if (check(mid)) l = ans = mid;
        else r = mid;
    }

    cout << round(ans);
    return 0;
}