[USACO09NOV]Job Hunt S 题解

题目描述

奶牛们没钱了，正在找工作。Farmer John 知道后，希望奶牛们四处转转，碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚\(D(1 \leq D \leq 1,000)\)美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵后又回来原来的城市 再最多赚D美元。而且这样往往返返的次数没有限制。 城市间有\(P (1 \leq P \leq 150)\)条单向路径连接，共有\(C(2 \leq C \leq 220)\)座城市，编号 \(1 \to C\). Bessie当前正在城市\(S (1 \leq S \leq C)\). 路径 i 从城市\(A_i\) 到城市\(B_i\) \((1 \leq A_i \leq C; 1 \leq B_i \leq C)\)，在路径上行走不用花任何费用。 为了帮助Bessie, Farmer John 让它使用他的私人飞机服务。这项服务可以飞行\(F\)条\((1 \leq F \leq 350)\)线路, 每条飞行线路是从城市\(J_i\)飞到另一座城市\(K_i (1 \leq J_i \leq C; 1 \leq K_i \leq C)\)，费用是\(T_i (1 \leq T_i \leq 50,000)\)美元. Bessie手中如果没有现钱，可以用以后赚的钱来付飞机票钱。 Bessie 可以任何时候，在任何城市选择退休。如果在时间上不作限制，Bessie总共可以赚多少钱呢？ 如果赚的钱也不会出现限制，就输出-1.

输入格式

第1行: 5个空格分开的整数 D, P, C, F, S 第2..P+1行: 第 i+1行包含2个空格分开的整数，表示一条从A_i 到 B_i的单向路径 第P+2..P+F+1行: 第P+i 包含3个空格分开的整数，表示一条从\(J_i\)到\(K_i\)的单向航线，费用为\(T_i\)

输出格式

第1行: 在上述规则下的最多可赚的钱数。

输入样例

100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120

输出样例

250

提示

Bessie 可以从城市 1 到 5 再到 2 ，最后到 3, 总共赚 4*100 - 150 = 250 美元.

此题的思路就是求一个最长路，走路的权值就是\(D\),开飞机的权值就是\(D-T\)，但是如果我们反着想，权值反着存，那不就成了最短路了吗？

#include <bits/stdc++.h>
using namespace std;
#define MAXN 255
#define MAXM 605
int cnt, D, P, C, F, S, flag, u, v, w, vis[MAXN], d[MAXN], head[MAXN];
struct node {
	int to, next, w;
}e[MAXM];
void adde(int u, int v, int w)
{
    e[++cnt].next = head[u];
	head[u] = cnt;
	e[cnt].to = v;
	e[cnt].w = w;
}
void dfs(int u)
{
    vis[u] = 1;
    int v;
    for(int i = head[u]; i; i = e[i].next)
		if(d[v = e[i].to] < d[u] + e[i].w + D)
		{
			if(vis[v])
			{
				flag = 1;
				return;
			}
			d[v] = d[u] + e[i].w + D;
			dfs(v);
			if(flag)
				return;
		}
	vis[u] = 0;
}
void spfa()
{
    d[S] = D;
    dfs(S);
}
int main()
{
    scanf("%d %d %d %d %d", &D, &P, &C, &F, &S);
    for(int i = 1; i <= P; i++)
    {
    	scanf("%d %d", &u, &v);
        adde(u, v, 0);
    }
    for(int i = 1; i <= F; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
        adde(u, v, -w);
    }
    spfa();
    if(!flag)
	{
		int ans = 0;
		for(int i = 1; i <= C; i++)
			ans = max(ans, d[i]);
		cout << ans << endl;
    }
    else
    {
    	puts("-1");
	}
    return 0;
}

洛谷数据太水没有-1的情况，但是写正解时肯定要加-1的情况的

[USACO09NOV]Job Hunt S 题解

原文：https://www.cnblogs.com/Quantum-Coke-Machine/p/13587831.html