本文主要是介绍zoj 3088 Easter Holidays，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个地点，以及m个上坡(lift)和k个下坡(slope)，按如下规则滑雪：
⑴从一个上坡的起点出发并最终回到起点。
⑵这个过程分为两个阶段：1.从起点走上坡到一点 2.从那一点走下坡回到起点。
⑶使得 走下坡所花时间和走上坡所花时间比值最大。
输出所经过路径和最大值。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdio>
#include <queue>using namespace std;const int inf = 100000000;
const int maxn = 1005;struct node{int v;int w;node(int _v, int _w){v = _v, w = _w;}
};int n,m,k;
vector<node> lista[maxn]; //下坡的邻接表
vector<node> listb[maxn]; //上坡的邻接表
int dist1[maxn]; //下坡
int path1[maxn];
int dist2[maxn]; //上坡
int path2[maxn];
bool inq[maxn]; //节点是否在队列中 void Input(){cin>>n>>m>>k;for(int i = 1; i <= n; i++) {lista[i].clear();listb[i].clear();}int u,v,w;for(int i = 0; i < m; i++){cin>>u>>v>>w;lista[v].push_back(node(u,w)); //逆边建图 }for(int i = 0; i < k; i++){cin>>u>>v>>w;listb[u].push_back(node(v,w));}
}void spfa1(int s){//下坡求最长路径 queue<int> q;for(int i = 1; i <= n; i++){path1[i] = -1;dist1[i] = -inf;inq[i] = false;}dist1[s] = 0;path1[s] = s;q.push(s);while(!q.empty()){int u = q.front(); q.pop(); inq[u] = false;for(int i = 0; i < lista[u].size(); i++){int v = lista[u][i].v;if(dist1[u] + lista[u][i].w > dist1[v]){dist1[v] = dist1[u] + lista[u][i].w;path1[v] = u;if(!inq[v]){//v不再队列中 q.push(v); inq[v] = true;}}}}}void spfa2(int s){//上坡求最短路径 queue<int> q;for(int i = 1; i <= n; i++){path2[i] = -1;dist2[i] = inf;inq[i] = false;}dist2[s] = 0;path2[s] = s;q.push(s);while(!q.empty()){int u = q.front(); q.pop(); inq[u] = false;for(int i = 0; i < listb[u].size(); i++){int v = listb[u][i].v;if(dist2[u] + listb[u][i].w < dist2[v]){dist2[v] = dist2[u] + listb[u][i].w;path2[v] = u;if(!inq[v]){//v不再队列中 q.push(v); inq[v] = true;}}}}}//求下坡比上坡的比值最大
void Solve(){vector<int> res1; //存储下坡的答案 vector<int> res2; //存储上坡的答案 double maximum = -inf;for(int i = 1; i <= n; i++){//从点i出发 spfa2(i);//上坡 spfa1(i);//下坡 for(int j = 1; j <= n; j++) {if(j == i) continue;if(dist1[j] / double(dist2[j]) > maximum){maximum = dist1[j] / double(dist2[j]);int now;//更新上坡的路径res2.clear();now = j;while(path2[now] != now){res2.push_back(now);now = path2[now];}res2.push_back(now);//更新下坡的路径 res1.clear();now = j;while(path1[now] != now){res1.push_back(now);now = path1[now];}res1.push_back(now);}}}//end of forfor(int i = res2.size()-1; i >= 0; i--){cout<<res2[i]<<" ";}for(int i = 1; i < res1.size()-1; i++){cout<<res1[i]<<" ";}cout<<res1[res1.size()-1]<<"\n";printf("%.3lf\n",maximum);
}int main(){int t;cin>>t;while(t--){Input();Solve();}return 0;
}思路：因为要走下坡所花时间和走上坡所花时间比值最大，所以走下坡所花时间要经可能的多， 而走上坡所花的时间要尽可能的少。对于上坡，对起点s求用spfa算法可求得s到其他点走上坡所花的最少时间dist2[i]；对于下坡，用逆边建图，然后用spfa算法可求得每一个点回到s所花费的最大时间dist1[i]。把dist1[i]/dist2[i]和maximum比较，更新maximum和路径。
代码：
这篇关于zoj 3088 Easter Holidays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
