题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;
const int N = 1010, M = 5000;
int h[N], ne[M], e[M], wt[M], wf[M], idx;
double dist[N];
bool st[N];
int q[M];   //循环队列
int n , m;
int Size[N];

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], wt[idx] = c, h[a] = idx ++ ;
}
bool spfa(double mid){
    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    memset(Size, 0, sizeof Size);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ ) q[tt ++ ] = i, st[i] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if(hh == M) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] < dist[t] + wf[t] - mid * wt[i]){
                dist[j] = dist[t] + wf[t] - mid * wt[i];
                Size[j] = Size[t] + 1;
                if (Size[j] >= n) return true;
                if (!st[j]){
                    q[tt ++ ] = j;
                    st[j] = true;
                    if (tt == M) tt = 0;
                }
           }
       }
    }

    return false;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> wf[i];

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c; 
        add(a, b, c);
    }
    double l = 0, r = 1010;
    while (r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if (spfa(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", l);

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla