MyException - 我的异常网
当前位置:我的异常网» 综合 » P1073 最优商业

P1073 最优商业

www.MyException.Cn  网友分享于:2013-09-07  浏览:0次
P1073 最优贸易

P1073 最优贸易

题目描述

C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。任意两个

城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路,一部分

为双向通行的道路,双向通行的道路在统计条数时也计为 1 条。

C 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价

格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息

之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城

市的标号从 1~ n,阿龙决定从 1 号城市出发,并最终在 n 号城市结束自己的旅行。在旅游的

过程中,任何城市可以重复经过多次,但不要求经过所有 n 个城市。阿龙通过这样的贸易方

式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品――水晶球,并在之后经过的另

一个城市卖出这个水晶球,用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游,他决定

这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。

假设 C 国有 5 个大城市,城市的编号和道路连接情况如下图,单向箭头表示这条道路

为单向通行,双向箭头表示这条道路为双向通行。

假设 1~n 号城市的水晶球价格分别为 4,3,5,6,1。

阿龙可以选择如下一条线路:1->2->3->5,并在 2 号城市以 3 的价格买入水晶球,在 3

号城市以 5 的价格卖出水晶球,赚取的旅费数为 2。

阿龙也可以选择如下一条线路 1->4->5->4->5,并在第 1 次到达 5 号城市时以 1 的价格

买入水晶球,在第 2 次到达 4 号城市时以 6 的价格卖出水晶球,赚取的旅费数为 5。

现在给出 n 个城市的水晶球价格,m 条道路的信息(每条道路所连接的两个城市的编号

以及该条道路的通行情况)。请你告诉阿龙,他最多能赚取多少旅费。

输入输出格式

输入格式:

 

第一行包含 2 个正整数 n 和 m,中间用一个空格隔开,分别表示城市的数目和道路的

数目。

第二行 n 个正整数,每两个整数之间用一个空格隔开,按标号顺序分别表示这 n 个城

市的商品价格。

接下来 m 行,每行有 3 个正整数,x,y,z,每两个整数之间用一个空格隔开。如果 z=1,

表示这条道路是城市 x 到城市 y 之间的单向道路;如果 z=2,表示这条道路为城市 x 和城市

y 之间的双向道路。

 

输出格式:

 

输出文件 trade.out 共 1 行,包含 1 个整数,表示最多能赚取的旅费。如果没有进行贸易,

则输出 0。

 

输入输出样例

输入样例#1:
5 5 
4 3 5 6 1 
1 2 1 
1 4 1 
2 3 2 
3 5 1 
4 5 2 
输出样例#1:
5

说明

【数据范围】

输入数据保证 1 号城市可以到达 n 号城市。

对于 10%的数据,1≤n≤6。

对于 30%的数据,1≤n≤100。

对于 50%的数据,不存在一条旅游路线,可以从一个城市出发,再回到这个城市。

对于 100%的数据,1≤n≤100000,1≤m≤500000,1≤x,y≤n,1≤z≤2,1≤各城市

水晶球价格≤100。

NOIP 2009 提高组 第三题

 

二、分析

 

第一步:正向spfa,找到每个从起点到i号城市能买到的物品的最低价c[i]
第二步:反向BFS,找到能卖东西的城市
第三步:用每个城市的卖出价减从起点到这个城市买东西的最低价就是获利,遍历所有城市,取最大获利

 

 

显然这道题目你只要找到任何路径上的最大值,最小值就好了; 
那么对于点k 
我们要知道1~k里面的最小值卖入; 
还要知道k~里面的最大值卖出; 
那么我们可以用spfa去求; 
第一遍跑出min数组后去反向图跑max数组; 
这样就好了; 
这道题目用缩点进行dp也可以;

 

首先能够买进卖出的地点一定与起点和终点连通 
我们可以从起点正向SPFA找出在可以走到的范围内能够买进的最小代价,然后从终点反向BFS找出哪些点能够走到终点,最后的答案是:

max(本地代价[i]-买进最小代价[i])(i能够走到终点)

  1 /*
  2 第一步:正向spfa,找到每个从起点到i号城市能买到的物品的最低价c[i] 
  3 第二步:反向BFS,找到能卖东西的城市 
  4 第三步:用每个城市的卖出价减从起点到这个城市买东西的最低价就是获利,遍历所有城市,取最大获利 
  5 */ 
  6 #include<bits/stdc++.h>
  7 using namespace std;
  8 const int oo=1e9;
  9 int q[1000001]={0},c[100001];
 10 bool vis[100001]={0},visf[100001]={0};
 11 int n,m,a[100001];
 12 int nedge=0,p[1000001],nex[1000001],head[100001];
 13 int nedgef=0,pf[1000001],nexf[1000001],headf[100001];
 14 
 15 //添加边  用于正向SPFA 
 16 //nex数组和head数组时用数组模拟链表
 17 //next[i]表示i下一个点的编号,head[i]表示i节点的所有能够到达的点
 18 //p[i]=b表示第i条边的终点是b点 
 19 inline void addedge(int a,int b){
 20     p[++nedge]=b;nex[nedge]=head[a];
 21     head[a]=nedge;
 22 }
 23 
 24 //添加边   用于反向BFS 
 25 //nexf数组和headf数组时用数组模拟链表
 26 //nexf[i]表示i下一个点的编号,headf[i]表示i节点的所有能够到达的点
 27 //pf[i]=b表示第i条边的终点是b点 
 28 inline void addedgef(int a,int b){
 29     pf[++nedgef]=b;nexf[nedgef]=headf[a];
 30     headf[a]=nedgef;
 31 }
 32 //第一步:正向spfa,找到每个从起点到i号城市能买到的物品的最低价c[i] 
 33 void spfa(){
 34     for(int i=1;i<=n;i++)c[i]=oo;
 35     //1号点被置为初始点,被置为访问过,并将它入队 
 36     vis[1]=1;q[1]=1;
 37     //队列的头尾指针都是1 
 38     int l=1,r=1;
 39     //如果尾小于等于头,也就是队列非空 
 40     while(l<=r){
 41         //把队头元素的值给now,并且对头指针加1 
 42         int now=q[l++];
 43         //遍历所有与now节点相连的元素 ,k表示now节点现在指的边 
 44         for(int k=head[now];k;k=nex[k]){
 45             //在 c[p[k]]和 c[now]和 a[now]取最小值给 c[p[k]](a[now]表示now号城市的商品价格) 
 46             //c数组是用来取商品价格最小值的 ,并且尾部的价格最低 
 47             int t=min(c[p[k]],min(c[now],a[now]));
 48             if(c[p[k]]>t){
 49                 c[p[k]]=t;
 50                 //p[k]表示k点到达的终点,如果k的终点没有被访问 
 51                 if(!vis[p[k]]){
 52                     //把它入队,并且置为访问过 
 53                     q[++r]=p[k];
 54                     vis[p[k]]=1;
 55                 }
 56             }   
 57         }
 58         //把now节点的访问标志置为0,方便now节点再次入队 
 59         vis[now]=0;
 60     }
 61 }
 62 //第二步:反向BFS,找到能卖东西的城市 
 63 void bfs(){
 64     //将q队列清0 
 65     memset(q,0,sizeof q);
 66     //将队列头尾指针都指向1,并且将n号城市入队 
 67     int l=1,r=1;q[1]=n;
 68     //如果队列非空 
 69     while(l<=r){
 70         //now取队头元素,队头指针++ 
 71         int now=q[l++];
 72         //k表示所有与now相连的边,pf[k]表示k对应边的终点 
 73         //如果边可以访问 
 74         for(int k=headf[now];k;k=nexf[k])if(!visf[pf[k]]){
 75             //把边的终点入队 
 76             q[++r]=pf[k];
 77             //将这个终点置为可以访问的 
 78             visf[pf[k]]=1;
 79         }
 80     }
 81 }
 82 //第三步:用每个城市的卖出价减从起点到这个城市买东西的最低价就是获利,遍历所有城市,取最大获利 
 83 int main()
 84 {
 85     scanf("%d%d",&n,&m);
 86     //a[i]表示城市i的商品价格 
 87     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 88     for(int i=1;i<=m;i++){
 89         //如果单向,就添加一条边,如果双向,就添加两条边 
 90         int x,y,z;scanf("%d%d%d",&x,&y,&z);
 91         addedge(x,y);addedgef(y,x);
 92         if(z==2)addedge(y,x),addedgef(x,y);
 93     }
 94     spfa();bfs();
 95     int ans=0;
 96     //遍历所有点,c[i]是从起点到i号城市买东西的最低价格,a[i]是i号城市物品的价格 
 97     for(int i=1;i<=n;i++)if(visf[i])ans=max(ans,a[i]-c[i]);
 98     printf("%d",ans);
 99     return 0;
100 }

 

文章评论

那些争议最大的编程观点
那些争议最大的编程观点
程序员必看的十大电影
程序员必看的十大电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老程序员的下场
老程序员的下场
一个程序员的时间管理
一个程序员的时间管理
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
漫画:程序员的工作
漫画:程序员的工作
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为什么程序员都是夜猫子
为什么程序员都是夜猫子
编程语言是女人
编程语言是女人
Java程序员必看电影
Java程序员必看电影
程序员的鄙视链
程序员的鄙视链
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
鲜为人知的编程真相
鲜为人知的编程真相
中美印日四国程序员比较
中美印日四国程序员比较
程序员和编码员之间的区别
程序员和编码员之间的区别
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
我是如何打败拖延症的
我是如何打败拖延症的
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
代码女神横空出世
代码女神横空出世
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
如何成为一名黑客
如何成为一名黑客
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
 程序员的样子
程序员的样子
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
我的丈夫是个程序员
我的丈夫是个程序员
程序员都该阅读的书
程序员都该阅读的书
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有