题解

01 分数规划

wt 点权
wf 边权

代码

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

using namespace std;

const int N = 1010, M = 5010;

int n,m;
int wf[N];
int h[N],e[M],wt[M],ne[M], idx;
double dist[N];
int q[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b,wt[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

bool check(double mid)
{
    memset(dist,0,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);

    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 == N) 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];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true; // find the circle;
                if(!st[j])
                {
                    q[tt ++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;

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

    memset(h,-1,sizeof h);
    for(int j = 0;j < m;j ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }

    double l = 0, r = 1e6;
    while(r - l > 1e-4)
    {
        double mid = (r + l) /2;// 忘记加括号，可恶
        if(check(mid)) l = mid;
        else r = mid;
    }

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

    return 0;
}