题目描述

Bessie is running out of money and is searching for jobs. Farmer John knows this and wants the cows to travel around so he has imposed a rule that his cows can only make D (1 <= D <= 1,000) dollars in a city before they must work in another city. Bessie can, however, return to a city after working elsewhere for a while and again earn the D dollars maximum in that city. There is no limit on the number of times Bessie can do this.
Bessie's world comprises P (1 <= P <= 150) one-way paths connecting C (2 <= C <= 220) cities conveniently numbered 1..C. Bessie is currently in city S (1 <= S <= C). Path i runs one-way from city Ai to city Bi (1 <= Ai <= C; 1 <= Bi <= C) and costs nothing to traverse.
To help Bessie, Farmer John will give her access to his private jet service. This service features F (1 <= F <= 350) routes, each of which is a one way flight from one city Ji to a another Ki (1 <= Ji <= C; 1 <= Ki <= C) and which costs Ti (1 <= Ti <= 50,000) dollars. Bessie can pay for the tickets from future earnings if she doesn't have the cash on hand.
Bessie can opt to retire whenever and wherever she wants. Given an unlimited amount of time, what is the most money that Bessie can make presuming she can make the full D dollars in each city she can travel to? Print -1 if there is no limit to this amount.

输入描述:

* Line 1: Five space-separated integers: D, P, C, F, and S
* Lines 2..P+1: Line i+1 contains two space-separated integers that name a one-way path from one city to another: Ai and Bi
* Lines P+2..P+F+1: Line P+i+1 contains three space-separated integers that name a one-way jet flight from one city to another and the price for that flight: Ji, Ki, and Ti

输出描述:

* Line 1: A single integer representing the most money she can make while following the law.

示例1

输入
100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120
输出
250
说明
This world has five cities, three paths and two jet routes. Bessie starts out in city 1, and she can only make 100 dollars in each city before moving on.
Bessie can travel from city 1 to city 5 to city 2 to city 3, and make a total of 4*100 - 150 = 250 dollars.

解答

这题好像很少有用弗洛伊德来做的？

但是的确可以。

在陆地上的路权值设为d

在空中的路权值设为d-费用

然后用floyed跑最长路

但是跑完对每个f[i][j]都要加上d，因为没有计算起点赚的钱

之后做两个判断，如果某个环里有起点

或者起点能到达的某个点在环里面

就输出-1

如果这两种情况都不存在就直接看从起点出发从哪个点结束钱最多

输出就行了

PS：判断某个环是否赚钱可以这么计算：

因为费用i到j

费用j到i

所以用是否大于0就能判断这个环能不能赚钱了 

#include<iostream>
#include<cstdio>
#include<cstring>
#define inv inline void
#define ini inline int
#define rint register int 
using namespace std;
int d,p,c,n,s,f[301][301];
int main()
{
    scanf("%d%d%d%d%d",&d,&p,&c,&n,&s);
    for (rint i=1;i<=c;i++)
        for (rint j=1;j<=c;j++)
            f[i][j]=-1000000000;
    for (rint i=1;i<=p;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        f[x][y]=d;
    }
    for (rint i=1;i<=n;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        f[x][y]=max(f[x][y],d-z);
    }
    for (rint i=1;i<=c;i++) f[i][i]=0;
    for (rint k=1;k<=c;k++)
        for (rint i=1;i<=c;i++)
            for (rint j=1;j<=c;j++)
                if (i!=j && j!=k && i!=k)
                    f[i][j]=max(f[i][j],f[i][k]+f[k][j]);
    for (rint i=1;i<=c;i++)
        for (rint j=1;j<=c;j++)
            f[i][j]+=d;
    for (rint i=1;i<=c;i++)
        if (f[s][i]+f[i][s]-2*d>0 && i!=s)
        {            
            cout<<-1;
            return 0;
        }
    for (rint i=1;i<=c;i++)
        for (rint j=1;j<=c;j++)
            if (i!=j && i!=s && j!=s)
                if (f[s][i]>-2000000 && f[i][j]+f[j][i]-2*d>0)
//350条航线，一条不超过50000元，就算再亏本也不会亏过1.75千万
                {
                    cout<<-1;
                    return 0;
                }
    int ans=0;
    for (rint i=1;i<=c;i++)
        ans=max(ans,f[s][i]);
    printf("%d",ans);
}


来源：xMinh