【題目鏈接】

ybt 1345：【例4-6】香甜的黃油
洛谷 P1828 [USACO3.2]香甜的黃油 Sweet Butter

【題目考點(diǎn)】

1. 圖論 最短路徑

【解題思路】

將題目敘述轉(zhuǎn)為圖論概念，牧場為頂點(diǎn)，牧場間的路線為邊。該題一個(gè)頂點(diǎn)上有多頭牛，這個(gè)后面再考慮。
記有V個(gè)頂點(diǎn)，E條邊，有n頭牛，每頭牛所在頂點(diǎn)為$v_1,v_2,...v_n$，$d(i,j)$為頂點(diǎn)i，j間的最短路徑長度。
題目要問的問題是，選擇一個(gè)頂點(diǎn)c，使得${\sum }_{i=1}^{n}d(v_i,c)$最小。
如果已知每頭牛所在頂點(diǎn)到其它任意頂點(diǎn)的最短路徑長度，那么接下來就可以遍歷所有頂點(diǎn)，記遍歷到的頂點(diǎn)為i，選擇頂點(diǎn)i為放糖的地方，求所有牛所在頂點(diǎn)到頂點(diǎn)i的最短路徑加和，這一步的復(fù)雜度為$O(V?n)$
問題落在如何求每頭牛所在頂點(diǎn)到其它任意頂點(diǎn)的最短路徑。

• 使用Floyd算法，求所有頂點(diǎn)間的最短路徑長度。題目給定頂點(diǎn)數(shù)（牧場數(shù)）最大為800，Floyd算法的復(fù)雜度為$O(V^3)$，$800^3=5.12?10^8$，運(yùn)算次數(shù)在$10^7$以下可以保證不會(huì)超時(shí)，復(fù)雜度達(dá)到$10^8$數(shù)量級很可能會(huì)超時(shí)，所以不能用Floyd算法。
  如果用單源最短路徑算法，需要對每頭牛所在頂點(diǎn)跑一次單源最短路徑算法。算法整體復(fù)雜度為：$O(n)$乘以所用的單源最短路徑算法的復(fù)雜度。
• 考慮使用樸素Dijkstra算法，整體復(fù)雜度為$O(n?V^2)$，計(jì)算$500?800^2=3.2?10^8$，不可行。
• 使用Dijkstra堆優(yōu)化算法，整體復(fù)雜度為$O(n?ElogE)$，題目中邊數(shù)最多約為1500，計(jì)算$500?1500?lo{g}_{2}1500\approx 8.25?10^6$，可行。
• 使用SPFA算法，復(fù)雜度為$O(kE)$，k為每個(gè)頂點(diǎn)平均入隊(duì)次數(shù)，在稀疏圖中一般小于2，可以認(rèn)為等于2。用SPFA算法做該問題，整體復(fù)雜度為$O(n?kE)$，計(jì)算$500?2?1500=1.5?10^6$，可行。

以上是思考過程，該題做法為：

通過Dijkstra堆優(yōu)化算法或SPFA算法求出每個(gè)牛所在頂點(diǎn)到其它所有頂點(diǎn)的最短路徑

遍歷每個(gè)頂點(diǎn)v，求每個(gè)牛所在頂點(diǎn)到v的最短路徑長度乘以那里牛的數(shù)量，再加和。求這些加和中的最小值。

【題解代碼】

解法1：Dijkstra堆優(yōu)化算法

#include<bits/stdc++.h> using namespace std; #define N 805 #define INF 0x3f3f3f3f struct Pair {int v, d;Pair(){}Pair(int a, int b):v(a),d(b){}bool operator < (const Pair &b) const{return b.d < d;} }; struct Edge {int t, w;Edge(){}Edge(int a, int b):t(a),w(b){} }; int n, p, c; bool vis[N]; int dis[N][N];//dis[i][j]:i到j(luò)的最短路徑長度 int place[N];//place[i]:牛i所在的頂點(diǎn) vector<Edge> edge[N]; void initGraph() {int f, t, w;cin >> n >> p >> c;for(int i = 1; i <= n; ++i)cin >> place[i];for(int i = 1; i <= c; ++i){cin >> f >> t >> w;edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void dijkstra(int v0) {memset(vis, 0, sizeof(vis));priority_queue<Pair> pq;dis[v0][v0] = 0;pq.push(Pair(v0, 0));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, w = edge[u][i].w;if(vis[v] == false && dis[v0][v] > dis[v0][u] + w){dis[v0][v] = dis[v0][u] + w;pq.push(Pair(v, dis[v0][v]));}}} } int main() {int v0, sum, ans = INF;initGraph();memset(dis, 0x3f, sizeof(dis));for(int i = 1; i <= n; ++i){v0 = place[i];//起點(diǎn) if(dis[v0][v0] == INF)//如果該頂點(diǎn)的單源最短路徑問題沒有求過了 dijkstra(v0);}for(int i = 1; i <= p; ++i){//在頂點(diǎn)i放糖 sum = 0;for(int j = 1; j <= n; ++j)sum += dis[place[j]][i];ans = min(ans, sum);}cout << ans;return 0; }

解法2：SPFA算法

#include<bits/stdc++.h> using namespace std; #define N 805 #define INF 0x3f3f3f3f struct Pair {int v, d;Pair(){}Pair(int a, int b):v(a),d(b){}bool operator < (const Pair &b) const{return b.d < d;} }; struct Edge {int t, w;Edge(){}Edge(int a, int b):t(a),w(b){} }; int n, p, c; bool vis[N]; int dis[N][N];//dis[i][j]:i到j(luò)的最短路徑長度 int place[N];//place[i]:牛i所在的頂點(diǎn) vector<Edge> edge[N]; void initGraph() {int f, t, w;cin >> n >> p >> c;for(int i = 1; i <= n; ++i)cin >> place[i];for(int i = 1; i <= c; ++i){cin >> f >> t >> w;edge[f].push_back(Edge(t, w));edge[t].push_back(Edge(f, w));} } void spfa(int v0) {memset(vis, 0, sizeof(vis));queue<int> que;dis[v0][v0] = 0;que.push(v0);vis[v0] = 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, w = edge[u][i].w;if(dis[v0][v] > dis[v0][u] + w){dis[v0][v] = dis[v0][u] + w;if(vis[v] == false){que.push(v);vis[v] = true;}}}} } int main() {int v0, sum, ans = INF;initGraph();memset(dis, 0x3f, sizeof(dis));for(int i = 1; i <= n; ++i){v0 = place[i];//起點(diǎn) if(dis[v0][v0] == INF)//如果該頂點(diǎn)的單源最短路徑問題沒有求過了 spfa(v0);}for(int i = 1; i <= p; ++i){//在頂點(diǎn)i放糖 sum = 0;for(int j = 1; j <= n; ++j)sum += dis[place[j]][i];ans = min(ans, sum);}cout << ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1345：【例4-6】香甜的黄油 | 洛谷 P1828 [USACO3.2]香甜的黄油 Sweet Butter的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。