luogu P1938 [USACO09NOV]找工就业Job Hunt

题目描述

奶牛们正在找工作。农场主约翰知道后,鼓励奶牛们四处碰碰运气。而且他还加了一条要求:一头牛在一个城市最多只能赚D(1≤D≤1000)美元,然后它必须到另一座城市工作。当然,它可以在别处工作一阵子后又回到原来的城市再最多赚D美元。而且这样的往返次数没有限制。

城市间有P(1≤P≤150)条单向路径连接,共有C(2≤C≤220)座城市,编号从1到C。奶牛贝茜当前处在城市S(1≤S≤C)。路径i从城市A_i到城市B_i(1≤A_i≤C,1≤B_i≤C),在路径上行走不用任何花费。

为了帮助贝茜,约翰让它使用他的私人飞机服务。这项服务有F条(1≤F≤350)单向航线,每条航线是从城市J_i飞到另一座城市K_i(1≤J_i≤C,1≤K_i≤C),费用是T_i(1≤T_i≤50000)美元。如果贝茜手中没有现钱,可以用以后赚的钱来付机票钱。

贝茜可以选择在任何时候,在任何城市退休。如果在工作时间上不做限制,贝茜总共可以赚多少钱呢?如果赚的钱也不会出现限制,就输出-1。

输入格式

第一行:5个用空格分开的整数D,P,C,F,S。

第2到第P+1行:第i+1行包含2个用空格分开的整数,表示一条从城市A_i到城市B_i的单向路径。

接下来F行,每行3个用空格分开的整数,表示一条从城市J_i到城市K_i的单向航线,费用是T_i。

输出格式

一个整数,在上述规则下最多可以赚到的钱数。

妙哉,大水题一道

把花钱当正边权,赚钱看成是负边权,跑最短路,即为求最大利润

spfa可以跑负边权图,还可以顺便判断负环,数据比较小,也不会被卡

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2e5+10;
int Next[N],head[N],go[N],w[N],tot;
inline void add(int u,int v,int o){
    Next[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=o;
}
bool vis[N];
int dis[N],in[N];
int d,n,m,f,s;
inline bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    queue<int>q;
    dis[s]=-d;
    q.push(s);
    while(q.size()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=Next[i]){
            int v=go[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(!vis[v]){
                    q.push(v),vis[v]=1,in[v]++;
                    if(in[v]==n)return 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    
    cin>>d>>m>>n>>f>>s;
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v,-d);
    }
    for(int i=1,u,v,o;i<=f;i++){
        scanf("%d%d%d",&u,&v,&o);
        add(u,v,o-d);
    }
    if(spfa())cout<<-1<<endl;
    else {
        int ans=0;
        for(int i=0;i<=n;i++)
        ans=min(ans,dis[i]);
        cout<<-ans<<endl;
    }
    
}
相关文章
相关标签/搜索