问题描述:

FJ的奶牛们找到了一张详细的城市地图,上面标注了城市中所有$L(2 <= L <= 1000)$座标志性建筑物(建筑物按1..L顺次编号),以及连接这些建筑物的$P(2 <= P <= 5000)$条单向道路。

FJ会开车将奶牛们送到某个她们指定的建筑物旁边,等奶牛们完成她们的整个旅行并回到出发点后,将她们接回农场。对于编号为i的标志性建筑物,奶牛们清楚地知道参观它能给自己带来的乐趣值$F_i (1 <= F_i <= 1000)$。 奶牛们同样仔细地研究过城市中的道路。她们知道第i条道路两端的建筑物$ L1_i$和$L2_i$ 以及她们从道路的一头走到另一头所需要的时间$T_i(1 <= T_i <= 1000)$

奶牛们希望她们在一整天中平均每单位时间内获得的乐趣值最大。当然咯,奶牛们不会愿意把同一个建筑物参观两遍,也就是说,虽然她们可以两次经过同一个建筑物,但她们的乐趣值只会增加一次。 请你写个程序,帮奶牛们计算一下她们能得到的最大平均乐趣值。

输入:

第一行两个整数L, P(见上文定义)
接下来L行,每行一个数$F_i $
接下来P行每行三个数:$ L1_i$,$L2_i$,$T_i$

输出:

一个两位小数,最大的单位时间平均乐趣。

思路:

比较简单的一道分数规划吧。二分答案,然后按照套路重新建图。新图上每条边的权值为$边权*mid-端点点权$,然后判断图中是否存在负环。

判断负环有一个特别巧妙的方法,就是跑一遍SPFA,记录松弛操作次数。如果操作次数大于了点的个数,那么就一定存在负环。

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <queue>
#define MAXN 1005
#define MAXE 5005
#define INF 2e9
#define eps 1e-4
using namespace std;

int n, m, cnt, f[MAXN], u[MAXE], v[MAXE], w[MAXE], head[MAXN], num[MAXN];
bool vis[MAXN];
double dis[MAXN];

struct Edge {int to, next; double dis;} edge[MAXE];

void addedge(int u, int v, double w)
{
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].dis=w;
    head[u]=cnt;
}

void init(double mid)
{
    cnt=0;
    memset(head, 0, sizeof(head));
    memset(num, 0, sizeof(num));
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<=n; i++) dis[i]=INF;
    for(int i=1; i<=m; i++) addedge(u[i], v[i], w[i]*mid-f[u[i]]);
}

bool spfa()
{
    queue<int> q;
    q.push(1); vis[1]=1; dis[1]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]>dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                num[to]=num[x]+1;
                if(num[to]>=n) return 0;
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
    return 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &f[i]);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &u[i], &v[i], &w[i]);
    double l=0, r=500000, mid;
    while(fabs(r-l)>eps)
    {
        mid=(l+r)/2;
        init(mid);
        if(spfa()) r=mid;
        else l=mid;
    }
    printf("%.2lf\n", mid);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注