首页 > 代码库 > zoj 3794 Greedy Driver
zoj 3794 Greedy Driver
给出n个点,m条有向边,Edward驾车要从点1到点n,车的满油量是c,在n个点中有p个点是加油站,Edward每到一个加油站都可以加满油(不用钱),每条边都有个权值L,表示通过这条边至少要有L个单位的油。然后题目给出了Q个点,在这Q个点Edward可以卖掉一些油,第qi个点油价格为vi,但是前提是他还能够到底第n个点,而且只能选择在Q个点中的一个点卖掉一些。题目则要求出Edward卖油所得钱的最大值。
对与Q个可以卖油的点,每个点可以得到(从1到qi最多剩多少油-从qi要到n点至少需要多少油)*vi。枚举则可得到最大值。而括号里的两个值,则可通过两次spfa求得(第二次要建反向图)。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxn=100005; 5 int n,m,c,p,q; 6 bool station[1005]; 7 bool inq[1005]; 8 struct edge{ 9 int v,w,p;10 edge(){}11 edge(int v,int w,int p):v(v),w(w),p(p){}12 }e[maxn<<1];13 int head1[1005],head2[1005];14 int d1[1005],d2[1005];15 int ecnt;16 void spfa(int st,int ed,int head[],int d[]){17 for(int i=1;i<=n;i++)d[i]=i==st?0:inf;18 queue<int>q;19 q.push(st);20 memset(inq,0,sizeof inq);21 inq[st]=1;22 while(!q.empty()){23 int u=q.front();q.pop();24 inq[u]=0;25 for(int i=head[u];i!=-1;i=e[i].p){26 int v=e[i].v;27 int tmp=d[u]+e[i].w;28 if(tmp<=c){29 if(station[v])tmp=0;//当当前点是加油站,则更新d[v]为0;30 if(tmp<d[v]){31 d[v]=tmp;32 if(!inq[v]){33 inq[v]=1;34 q.push(v);35 }36 }37 }38 }39 }40 }41 void run(){42 memset(head1,-1,sizeof head1);43 memset(head2,-1,sizeof head2);44 ecnt=0;45 while(m--){46 int u,v,w;47 scanf("%d%d%d",&u,&v,&w);48 if(w>c)continue;49 e[ecnt]=edge(v,w,head1[u]);50 head1[u]=ecnt++;51 e[ecnt]=edge(u,w,head2[v]);//建反向边52 head2[v]=ecnt++;53 }54 scanf("%d",&p);55 memset(station,0,sizeof station);56 while(p--){57 int x;58 scanf("%d",&x);59 station[x]=1; //标记加油站60 }61 spfa(1,n,head1,d1);62 spfa(n,1,head2,d2);//两次spfa63 int ans=0;64 scanf("%d",&q);65 while(q--){66 int x,v;67 scanf("%d%d",&x,&v);68 if(c-d1[x]-d2[x]>0)ans=max(ans,(c-d1[x]-d2[x])*v);//对于Q个卖油点,更新答案69 }70 if(d1[n]==inf)ans=-1;//不能到达,输出-171 cout<<ans<<endl;72 }73 int main()74 {75 // freopen("in","r",stdin);76 while(cin>>n>>m>>c)run();77 return 0;78 }
zoj 3794 Greedy Driver
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。