首页 > 代码库 > ZOJ3794 Greedy Driver [BFS]
ZOJ3794 Greedy Driver [BFS]
题目地址: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3794
题目描述:
N个城市，M条有向边。要从城市1开车到城市N，中途可以加油，也可以倒卖一次油，问最多能赚多少钱。
油箱容量是C。N个城市中有P个城市（p1, p2…）可以任意免费加油； 有Q个城市（q1,q2…），可以卖油（价格为pri1,pri2…），但全程只能在一座城市卖一次油；每条边都会消耗一定的油。在一开始，油箱是满的。如果能从城市1到达城市N，输出最多可以赚的钱，否则输出-1。
解题思路:
一开始读错题还在考虑遍历城市的问题，后来发现不用遍历每座城市。。于是问题就很简单了。因为只能卖一次油，状态也很好保存。
每个节点（城市）维护一下几个值：
isReachable - 是否能从城市1走到
isPassable – 在装满油箱时，能否从这个城市走到城市N
leastUnit – 从这个城市走到城市N，一开始至少要装多少油
pendingMaxUnit – 走过这座城市时，在还没有卖过油的状态下，油箱最多能剩多少油
soldMaxEarn – 走过这座城市时，已经曾经卖过一次油，并且当前的剩余油量不低于leastUnit的条件下，赚到最多的钱
isFuelStation – 是否可以加油
canSellFuel – 是否可以卖油
price – 如果可以卖油，每单位的油价
首先从城市N反向跑一个BFS，标记isPassable并计算出leastUnit。
再从城市1跑一个BFS，计算出isReachable，pendingMaxUnit，soldMaxEarn。
源代码：
1 //zoj3794_zzy_2014.07.15_AC_graph BFS_DP 2 #include <iostream> 3 #include <queue> 4 5 using namespace std; 6 7 class Edge 8 { 9 public: 10 Edge(int v, int c, Edge *p): vid(v), cost(c), next(p) {} 11 int vid, cost; 12 Edge *next; 13 }; 14 15 class Vertex 16 { 17 public: 18 Vertex() {} 19 bool isReachable; //can through the beginning to this vertex with capacity C. 20 bool isPassable; //can through this vertex to the end with the capacity C. 21 int leastUnit; //from this vertex to the end, need at least leastUnit unit fuel. leastUnit can be larger than maximum capacity C. 22 int pendingMaxUnit; //when pass this vertex and never sold fuel, the maximum left unit of fuel. This can be less than leastUnit. 23 int soldMaxEarn; //when pass this vertex and sold fuel and left fuel no less than leastUnit, the maximum money earned. 24 bool isFuelStation; 25 bool canSellFuel; 26 int price; 27 Edge *ep; 28 Edge *bep; 29 }; 30 31 class GreedyDriver 32 { 33 public: 34 GreedyDriver(int n, int m, int c): N(n), M(m), C(c) { 35 for(int idx = 1; idx <= N; ++idx) { 36 graph[idx].isReachable = false; 37 graph[idx].isPassable = false; 38 graph[idx].leastUnit = -1; 39 graph[idx].pendingMaxUnit = -1; 40 graph[idx].soldMaxEarn = -1; 41 graph[idx].isFuelStation = false; 42 graph[idx].canSellFuel = false; 43 graph[idx].price = 0; 44 graph[idx].ep = NULL; 45 graph[idx].bep = NULL; 46 } 47 } 48 ~GreedyDriver() { 49 for(int idx = 1; idx <= N; ++idx) { 50 Edge *p = graph[idx].ep; 51 while(p != NULL) { 52 Edge *q = p; 53 p = p -> next; 54 delete q; 55 } 56 } 57 } 58 void construct(); 59 void solve(); 60 int ans(); 61 private: 62 int N,M,C; 63 Vertex graph[1001]; 64 void iniLeastUnit(); 65 void BFS(); 66 }; 67 68 void GreedyDriver::construct() 69 { 70 for(int idx = 1; idx <= M; ++idx) { 71 int s, t, l; 72 cin >> s >> t >> l; 73 Edge *p = new Edge(t, l, graph[s].ep); 74 graph[s].ep = p; 75 Edge *q = new Edge(s, l, graph[t].bep); 76 graph[t].bep = q; 77 } 78 int P; 79 cin >> P; 80 while(P--) { 81 int vid; 82 cin >> vid; 83 graph[vid].isFuelStation = true; 84 } 85 int Q; 86 cin >> Q; 87 while(Q--) { 88 int vid, pri; 89 cin >> vid >> pri; 90 graph[vid].canSellFuel = true; 91 graph[vid].price = pri; 92 } 93 } 94 95 int GreedyDriver::ans() 96 { 97 if(graph[N].isReachable == false) 98 return -1; 99 int maxEarn = 0;100 for(int idx = 1; idx <= N; ++idx) {101 if(graph[idx].isReachable && graph[idx].isPassable && graph[idx].soldMaxEarn > maxEarn)102 maxEarn = graph[idx].soldMaxEarn;103 }104 return maxEarn;105 }106 107 void GreedyDriver::iniLeastUnit()108 {109 bool inQueue[1001];110 for(int idx = 1; idx <= N; ++idx)111 inQueue[idx] = false;112 graph[N].leastUnit = 0;113 queue<int> Q;114 while(!Q.empty()) Q.pop();115 Q.push(N);116 inQueue[N] = true;117 while(!Q.empty()) {118 int fid = Q.front();119 Q.pop();120 inQueue[fid] = false;121 int fLeastUnit = graph[fid].isFuelStation ? 0 : graph[fid].leastUnit;122 Edge *p = graph[fid].bep;123 while(p != NULL) {124 int sid = p -> vid;125 int sLeastUnit = fLeastUnit + p -> cost;126 if(graph[sid].leastUnit == -1 || graph[sid].leastUnit > sLeastUnit) {127 graph[sid].leastUnit = sLeastUnit;128 if(graph[sid].leastUnit <= C)129 graph[sid].isPassable = true;130 if(graph[sid].isPassable && inQueue[sid] == false) {131 Q.push(sid);132 inQueue[sid] = true;133 }134 }135 p = p-> next;136 }137 }138 }139 140 void GreedyDriver::BFS()141 {142 bool inQueue[1001];143 for(int idx = 1; idx <= N; ++idx)144 inQueue[idx] = false;145 if(graph[1].isPassable == false)146 return;147 graph[1].isReachable = true;148 graph[1].pendingMaxUnit = C;149 if(graph[1].canSellFuel) {150 if(graph[1].isFuelStation)151 graph[1].soldMaxEarn = C * graph[1].price;152 else if(graph[1].pendingMaxUnit > graph[1].leastUnit)153 graph[1].soldMaxEarn = (graph[1].pendingMaxUnit - graph[1].leastUnit) * graph[1].price;154 }155 queue<int> Q;156 while(!Q.empty()) Q.pop();157 Q.push(1);158 inQueue[1] = true;159 while(!Q.empty()) {160 int fid = Q.front();161 Q.pop();162 inQueue[fid] = false;163 Edge *p = graph[fid].ep;164 while(p != NULL) {165 int sid = p -> vid;166 if(graph[sid].isPassable) {167 if(graph[fid].pendingMaxUnit - (p -> cost) >= (graph[sid].isFuelStation ? 0 : graph[sid].leastUnit)) {168 if(graph[sid].isReachable == false) {169 Q.push(sid);170 inQueue[sid] = true;171 }172 graph[sid].isReachable = true;173 if(graph[sid].isFuelStation)174 graph[sid].pendingMaxUnit = C;175 else {176 if(graph[fid].pendingMaxUnit - (p -> cost) > graph[sid].pendingMaxUnit) {177 graph[sid].pendingMaxUnit = graph[fid].pendingMaxUnit - (p -> cost);178 if(inQueue[sid] == false)179 Q.push(sid);180 inQueue[sid] = true;181 }182 }183 if(graph[sid].canSellFuel) {184 if(graph[sid].isFuelStation)185 graph[sid].soldMaxEarn = C * graph[sid].price;186 else if(graph[sid].pendingMaxUnit > graph[sid].leastUnit &&187 (graph[sid].pendingMaxUnit - graph[sid].leastUnit) * graph[sid].price > graph[sid].soldMaxEarn)188 graph[sid].soldMaxEarn = (graph[sid].pendingMaxUnit - graph[sid].leastUnit) * graph[sid].price;189 }190 }191 }192 p = p-> next;193 }194 }195 }196 197 void GreedyDriver::solve()198 {199 graph[1].isReachable = true;200 graph[N].isPassable = true;201 iniLeastUnit();202 BFS();203 }204 205 int main()206 {207 int n,m,c;208 while(cin >> n >> m >> c) {209 GreedyDriver *gd = new GreedyDriver(n, m, c);210 gd -> construct();211 gd -> solve();212 cout << gd -> ans() << endl;213 delete gd;214 }215 return 0;216 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。