【題目鏈接】

ybt 1344：【例4-4】最小花費
洛谷 P1576 最小花費

【題目考點】

1. 圖論 單源最短路徑

時間復雜度：
Dijkstra算法: $O(V^2)$
Dijkstra堆優化算法: $O(V^2)$
SPFA算法:$O(kE)$ ~ $O(VE)$
空間復雜度：
鄰接矩陣：$O(V^2)$，
鄰接表：$O(V+E)$

【解題思路】

設A有x元要轉給B，B收到y元，手續費費率為z，那么有$y=x?x?z\%$
如果已知B要得到y元，A要給B轉賬x元才能滿足要求，則有$x=\frac{y}{1?z\%}$
記$c=\frac{1}{1?z\%}$，稱c為費用系數，那么$x=c?y$
回顧Dijkstra與spfa算法中的松弛操作：
u是v的鄰接點，邊(u,v)的權值為w(u,v)，當前已知從起點v0到v和u的最短路徑長度分別為dis[v]與dis[u]。
如果dis[v] > dis[u] + w(u,v)，那么dis[v] = dis[u] + w(u,v)。
該題中，松弛操作與上述方法類似，但又有所不同。
設數組mo，mo[i]表示要使B得到100元，i需要花的最少錢數。已知v和u是鄰接點，二者間轉賬的費用系數為c(u,v)，
原有一條從v轉賬到B的路徑，需要v提供mo[v]元。現在新發現一條從u轉賬到B的路徑，需要u提供mo[u]元，如果從v轉賬到u，再走從u到B的路徑，需要v提供mo[u]*c(u,v)
如果mo[v]大于mo[u]*c(u,v)，說明v先轉賬到u再通過一條路徑轉到B，這樣的方案可以使v提供更少的費用。
所以松弛操作為：如果mo[v] > mo[u]*c(u,v)，那么mo[v] = mo[u]*c(u,v)
其余操作和原算法相同。

【題解代碼】

解法1：Dijkstra算法

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Edge {int t;double c;//費用系數。x元錢費率z%轉賬給y,y = x - x*z%，則x = y / (1-z%)。記費用系數c為1/(1-z%)，那么x = c*y Edge(){}Edge(int a, double b):t(a),c(b){} }; vector<Edge> edge[N]; int n, m, a, b; bool vis[N]; double mo[N];//mo[i]:要使b得到100元，i需要提供的錢數 void initGraph() {int f, t, z;double c;//費用系數 cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> z;c = 1 / (1 - z / 100.0);edge[f].push_back(Edge(t, c));edge[t].push_back(Edge(f, c));}cin >> a >> b; } void dijkstra() {memset(mo, 0x43, sizeof(mo));//將mo各元素設為無窮大mo[b] = 100;for(int k = 1; k <= n; ++k){int u = 0;for(int i = 1; i <= n; ++i){if(vis[i] == false && (u == 0 || mo[i] < mo[u]))u = i;}vis[u] = true;for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t;double c = edge[u][i].c;if(vis[v] == false && mo[v] > mo[u] * c)mo[v] = mo[u] * c;}} } int main() {initGraph();dijkstra();cout << fixed << setprecision(8) << mo[a];return 0; }

解法2：SPFA算法

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Edge {int t;double c;//費用系數。x元錢費率z%轉賬給y,y = x - x*z%，則x = y / (1-z%)。記費用系數c為1/(1-z%)，那么x = c*y Edge(){}Edge(int a, double b):t(a),c(b){} }; vector<Edge> edge[N]; int n, m, a, b; bool vis[N]; double mo[N];//mo[i]:要使b得到100元，i需要提供的錢數 void initGraph() {int f, t, z;double c;//費用系數 cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> z;c = 1 / (1 - z / 100.0);edge[f].push_back(Edge(t, c));edge[t].push_back(Edge(f, c));}cin >> a >> b; } void spfa() {memset(mo, 0x43, sizeof(mo));//將mo各元素設為無窮大queue<int> que;mo[b] = 100;que.push(b);vis[b] = true;while(que.empty() == false){int u = que.front();que.pop();vis[u] = false;for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t;double c = edge[u][i].c;if(mo[v] > mo[u] * c){mo[v] = mo[u] * c;if(vis[v] == false){que.push(v);vis[v] = true;}}}} } int main() {initGraph();spfa();cout << fixed << setprecision(8) << mo[a];return 0; }

解法3：Dijkstra堆優化算法

#include<bits/stdc++.h> using namespace std; #define N 2005 struct Pair {int v;//頂點 double d;//距離 bool operator < (const Pair &b) const{return b.d < d;}Pair(){}Pair(int a, double b):v(a),d(b){} }; struct Edge {int t;double c;//費用系數。x元錢費率z%轉賬給y,y = x - x*z%，則x = y / (1-z%)。記費用系數c為1/(1-z%)，那么x = c*y Edge(){}Edge(int a, double b):t(a),c(b){} }; vector<Edge> edge[N]; int n, m, a, b; bool vis[N]; double mo[N];//mo[i]:要使b得到100元，i需要提供的錢數 void initGraph() {int f, t, z;double c;//費用系數 cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t >> z;c = 1 / (1 - z / 100.0);edge[f].push_back(Edge(t, c));edge[t].push_back(Edge(f, c));}cin >> a >> b; } void dijkstra() {priority_queue<Pair> pq;memset(mo, 0x43, sizeof(mo));//將mo各元素設為無窮大mo[b] = 100;pq.push(Pair(b, mo[b]));while(pq.empty() == false){int u = pq.top().v;pq.pop();if(vis[u])continue;vis[u] = true;for(int i = 0; i < edge[u].size(); ++i){int v = edge[u][i].t;double c = edge[u][i].c;if(vis[v] == false && mo[v] > mo[u] * c){mo[v] = mo[u] * c;pq.push(Pair(v, mo[v]));}}} } int main() {initGraph();dijkstra();cout << fixed << setprecision(8) << mo[a];return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1344：【例4-4】最小花费 | 洛谷 P1576 最小花费的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。