首页 > 代码库 > 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