【题目链接】ybt 1345【例4-6】香甜的黄油洛谷 P1828 [USACO3.2]香甜的黄油 Sweet Butter【题目考点】1. 图论 最短路径【解题思路】将题目叙述转为图论概念牧场为顶点牧场间的路线为边。道路是双向的因此该图是无向图。该题一个顶点上有多头牛这个后面再考虑。记有V VV个顶点E EE条边有n nn头牛每头牛所在顶点为v 1 , v 2 , . . . v n v_1,v_2,...v_nv1​,v2​,...vn​d ( i , j ) d(i,j)d(i,j)为顶点ij间的最短路径长度。题目要问的问题是选择一个顶点c cc使得∑ i 1 n d ( v i , c ) \sum_{i1}^nd(v_i,c)∑i1n​d(vi​,c)最小。遍历所有顶点遍历到顶点i ii时选择顶点i ii为放糖的地方需要求所有牛所在顶点到顶点i ii的最短路径加和。由于该图是无向图顶点u uu到顶点i ii的最短路径长度就是顶点i ii到顶点u uu的最短路径长度。可以先使用单源最短路径算法求出顶点i ii到其它顶点的最短路径长度而后再遍历每t牛所在的顶点求出顶点i ii到每头问题落在如何求每头牛所在顶点到其它任意顶点的最短路径。使用Floyd算法求所有顶点间的最短路径长度。题目给定顶点数牧场数最大为800Floyd算法的复杂度为O ( V 3 ) O(V^3)O(V3)800 3 5.12 ∗ 10 8 800^35.12*10^880035.12∗108运算次数在10 8 10^8108以下可以保证不会超时复杂度达到10 8 10^8108数量级很可能会超时所以不能用Floyd算法。如果用单源最短路径算法需要对每头牛所在顶点跑一次单源最短路径算法。算法整体复杂度为O ( n ) O(n)O(n)乘以所用的单源最短路径算法的复杂度。考虑使用朴素Dijkstra算法整体复杂度为O ( n ⋅ V 2 ) O(n\cdot V^2)O(n⋅V2)计算次数为500 ∗ 800 2 3.2 ∗ 10 8 500*800^23.2*10^8500∗80023.2∗108不可行。使用Dijkstra堆优化算法整体复杂度为O ( n ⋅ E l o g E ) O(n\cdot ElogE)O(n⋅ElogE)题目中边数最多约为1500计算500 ∗ 1500 ∗ l o g 2 1500 ≈ 8.25 ∗ 10 6 500*1500*log_21500\approx8.25*10^6500∗1500∗log2​1500≈8.25∗106可行。使用SPFA算法复杂度为O ( k E ) O(kE)O(kE)k为每个顶点平均入队次数在稀疏图中一般小于2可以认为等于2。用SPFA算法做该问题整体复杂度为O ( n ⋅ k E ) O(n\cdot kE)O(n⋅kE)计算500 ∗ 2 ∗ 1500 1.5 ∗ 10 6 500*2*1500 1.5*10^6500∗2∗15001.5∗106可行。以上是思考过程该题做法为通过Dijkstra堆优化算法或SPFA算法求出每个牛所在顶点到其它所有顶点的最短路径遍历每个顶点v求每个牛所在顶点到v的最短路径长度乘以那里牛的数量再加和。求这些加和中的最小值。【题解代码】解法1Dijkstra堆优化算法#includebits/stdc.husingnamespacestd;#defineN805#defineINF0x3f3f3f3fstructPair{intv,d;Pair(){}Pair(inta,intb):v(a),d(b){}booloperator(constPairb)const{returnb.dd;}};structEdge{intt,w;Edge(){}Edge(inta,intb):t(a),w(b){}};intn,p,c;boolvis[N];intdis[N][N];//dis[i][j]:i到j的最短路径长度intplace[N];//place[i]:牛i所在的顶点vectorEdgeedge[N];voidinitGraph(){intf,t,w;cinnpc;for(inti1;in;i)cinplace[i];for(inti1;ic;i){cinftw;edge[f].push_back(Edge(t,w));edge[t].push_back(Edge(f,w));}}voiddijkstra(intv0){memset(vis,0,sizeof(vis));priority_queuePairpq;dis[v0][v0]0;pq.push(Pair(v0,0));while(pq.empty()false){intupq.top().v;pq.pop();if(vis[u])continue;vis[u]true;for(inti0;iedge[u].size();i){intvedge[u][i].t,wedge[u][i].w;if(vis[v]falsedis[v0][v]dis[v0][u]w){dis[v0][v]dis[v0][u]w;pq.push(Pair(v,dis[v0][v]));}}}}intmain(){intv0,sum,ansINF;initGraph();memset(dis,0x3f,sizeof(dis));for(inti1;in;i){v0place[i];//起点if(dis[v0][v0]INF)//如果该顶点的单源最短路径问题没有求过了dijkstra(v0);}for(inti1;ip;i){//在顶点i放糖sum0;for(intj1;jn;j)sumdis[place[j]][i];ansmin(ans,sum);}coutans;return0;}解法2SPFA算法#includebits/stdc.husingnamespacestd;#defineN805#defineINF0x3f3f3f3fstructPair{intv,d;Pair(){}Pair(inta,intb):v(a),d(b){}booloperator(constPairb)const{returnb.dd;}};structEdge{intt,w;Edge(){}Edge(inta,intb):t(a),w(b){}};intn,p,c;boolvis[N];intdis[N][N];//dis[i][j]:i到j的最短路径长度intplace[N];//place[i]:牛i所在的顶点vectorEdgeedge[N];voidinitGraph(){intf,t,w;cinnpc;for(inti1;in;i)cinplace[i];for(inti1;ic;i){cinftw;edge[f].push_back(Edge(t,w));edge[t].push_back(Edge(f,w));}}voidspfa(intv0){memset(vis,0,sizeof(vis));queueintque;dis[v0][v0]0;que.push(v0);vis[v0]true;while(que.empty()false){intuque.front();que.pop();vis[u]false;for(inti0;iedge[u].size();i){intvedge[u][i].t,wedge[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;}}}}}intmain(){intv0,sum,ansINF;initGraph();memset(dis,0x3f,sizeof(dis));for(inti1;in;i){v0place[i];//起点if(dis[v0][v0]INF)//如果该顶点的单源最短路径问题没有求过了spfa(v0);}for(inti1;ip;i){//在顶点i放糖sum0;for(intj1;jn;j)sumdis[place[j]][i];ansmin(ans,sum);}coutans;return0;}