首页 > 其他分享 >洛谷题解-P1938 [USACO09NOV] Job Hunt S

洛谷题解-P1938 [USACO09NOV] Job Hunt S

时间:2024-01-28 19:11:06浏览次数:33  
标签:USACO09NOV 洛谷 int 题解 城市 贝茜 Bessie 边权 dis

https://www.luogu.com.cn/problem/P1938

题目描述

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 A_i to city B_i (1 <= A_i <= C; 1 <= B_i <= 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 J_i to a another K_i (1 <= J_i <= C; 1 <= K_i <= C) and which costs T_i (1 <= T_i <= 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.

奶牛们正在找工作。农场主约翰知道后,鼓励奶牛们四处碰碰运气。而且他还加了一条要求:一头牛在一个城市最多只能赚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。

输出格式

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

输入输出样例

输入 #1
100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120
输出 #1
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.

Source: USACO 2009 November Silver

这个世界上有五个城市,三条单向路径和两条单向航线。贝茜从一号城市开始她的旅行,她在离开一个城市前最多只能在这个城市赚100美元。

贝茜可以通过从一号城市-->五号城市-->二号城市-->三号城市的旅行赚到4*100-150=250美元。

(注:在四个城市各赚100美元,从五号城市飞到二号城市花掉150美元)

来源:USACO 2009 十一月银组

 

最短路好题!!!

1.化点权为边权,又有点权还有边权,可以都化为边权

2.这题是最长路,但是可以将每条边权取反,不就是最短路了吗!?最后答案也要取反

3.起点的值设置详情(往下解释)

 

思路还是很好想到的,走到的点建边,权值是d(把进过每个点的点权D融到边权中,因为题目设定边权为0,所以刚好可以转换)

飞到的点也要建边,边权是负数(减去一个金钱嘛,那就是,但是进过一个点又要加点权d,所以我们这样写 -(w-d),化简,得d-w)

但是!!这题要求求出最长路(金钱最多嘛),我们可以考虑把所有权值取反(走 -d  飞 w-d),跑一遍最短路,注意一下答案要取反

因为起点1的点有点权,是d,最后答案还要加d,但是dis[s]=d是错的!!!!因为这里设初值会影响后面跑最短路,所以起点点权是最后答案再加上去!!!!!

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
struct node
{
	int v, w;
};
int d, m, n, f, s, u1, v1, w1, dis[N], vis[N], ans=INT_MAX, cnt[N];
vector<node> a[N];
queue<int> q;
bool spfa(int s)
{
    memset(dis, 63, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    dis[s]=0;
    cnt[s]=1;
    q.push(s);
     
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
         
        for (int i=0; i<a[u].size(); i++)
        {
            int v=a[u][i].v, w=a[u][i].w;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if (!vis[v])
                {
                    q.push(v), vis[v]=1, cnt[v]++;
                    if (cnt[v]>n) return true;
                }
            }
        }
    }
    return false;
}
int main()
{
	scanf("%d%d%d%d%d", &d, &m, &n, &f, &s);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d", &u1, &v1);
		a[u1].push_back({v1, -d}); //取反了
	}
	for (int i=1; i<=f; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1-d}); //取反了
	}
	if (spfa(s)) //有负环
	{
		printf("-1");
		return 0;
	}
	
	for (int i=1; i<=n; i++) 	
		ans=min(ans, dis[i]); //取最小值(取max取反为取min。要求最长路,所以取min)
	printf("%d", -ans+d); //ans取反,加初始点点权d
	return 0;
}

 

标签:USACO09NOV,洛谷,int,题解,城市,贝茜,Bessie,边权,dis
From: https://www.cnblogs.com/didiao233/p/17993155

相关文章

  • ATtokiomarine2020E O(rand) 题解
    题目链接点击打开链接题目解法首先,\(S\)一定要是\(T\)的子集先筛出符合条件的\(a_i\),即满足\(S\subseteqa_i\subseteqT\)令\(dif\)为\(T-S\),定义数\(x\)覆盖第\(y\)位为二进制下\(x\)的第\(y\)位为\(1\)现在的问题变成了找到大小\(\lek\)的\(\{a_i\}......
  • 洛谷题解-P2888 [USACO07NOV] Cow Hurdles S (Floyd)
    https://www.luogu.com.cn/problem/P2888题目描述FarmerJohnwantsthecowstoprepareforthecountyjumpingcompetition,soBessieandthegangarepracticingjumpingoverhurdles.Theyaregettingtired,though,sotheywanttobeabletouseaslittleene......
  • ABC338 F Negative Traveling Salesman 题解
    QuestionABC338FNegativeTravelingSalesman给出一个\(N\)个点\(M\)条边的有向图,边权可能为负数,但不可能有负环每经过一条边就要加上这条边的代价求,一条路径经过所有的点,并且要求总代价最小Solution观察到\(N\le20\)自然而然想到状压因为多次经过一条边的代价是......
  • [洛谷]美化
    洛谷美化指南\(\color{pink}\mathbf{大家好,相比很多洛谷党都觉得洛谷的界面特别单一(丑陋)。}\)\(\color{red}\mathbf{那我们就可以借助一下这个东西:Tampermonkey。(注:在扩展商店里搜索英文名)}\)1.安装“篡改猴Tampermonkey”网址:Tampermonkey2.安装脚本:氢洛谷下载脚本:氢洛谷......
  • CF1423G Growing flowers题解
    考虑每种颜色的贡献,用总数\(n-k+1\)减去没有贡献到的(极长连续段长度为\(len\)时),贡献为\(\max(len-k+1,0)\),所以考虑用\(\text{ODT}\)维护所有颜色的连续段。具体的,维护一个大的\(ODT\)存储所有连续段,再对每个颜色存储自己的连续段,用\(\text{BIT}\)维护每个长度的极长......
  • ABC338 D Island Tour 题解
    Question有\(n\)座海岛由\(n\)条桥连着,第\(i\)座桥连接第\(i\)和\(i+1\)座海岛,第\(n\)座桥连接第\(n\)和\(1\)座海盗有一条长度为\(m\)的旅游路线,第\(X_i\)表示依次到达的岛屿现在需要切断一条桥,求总旅游路线最小值Solution显然,从第\(X_{i-1}\)到\(X_......
  • ABC338 E Chords 题解
    Question一个圆上有\(2N\)个点均匀分布,给出\(N\)条线,每条线连接两个顶点问,有没有两条线相交Solution也算一个比较典的题目考虑到这种两两配对,配对中有没有交错关系的可以考虑异或哈希因为一个数异或两次等于它本身,所以我们可以用异或来实现一个“撤销”操作我们当我......
  • UVA10852 的题解
    UVA10852的题解题目大意给定自然数\(n(100\leqn\leq10000)\),寻找质数\(x\len\),使得\(p\timesx\leqn<(p+1)\timesx\)且\(n-p\timesx\)最大。思路不难发现,\(p\)其实就是$\left\lfloor\frac{n}{x}\right\rfloor$,所以,我们只要找到对应的\(x\),\(p\)的只就......
  • 洛谷题解-P3003 [USACO10DEC] Apple Delivery S (dijkstra)
    题目描述Bessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumb......
  • CF765F Souvenirs 题解
    题目链接:CF或者洛谷想了很久,然后想起做过的一道题:秃子酋长,一开始以为差不多,结果写着写着就发现不对劲了。最后写出了个神仙回滚莫队解法,感觉很妙,记录下。进入神仙分析时刻首先,我们来考虑一个事实,加上一个数以后,如果能找到它的前后驱,那么可以立马更新最优解,这个也即是瓶颈点。......