题目链接:点击打开链接
题意:有n个绿洲, m条道路,每条路上有一个温度,和一个路程长度,从绿洲s到绿洲t,求一条道路的最高温度尽量小, 如果有多条, 选一条总路程最短的。
思路:先生成最小生成树,按照温度排序, 当s和t联通的时候, 这个温度就是最高温度。 然后把其他温度小于等于这个温度的道路也加进图中, 跑一个最短路就行了。
细节参见代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const double INF = 1000000000.0; const int maxn = 100 + 10; int T,n,m,S,p[maxn],path[maxn]; double ans_t,ans_l,d[maxn]; bool done[maxn], vis[maxn*maxn]; struct node { int a, b; double r, d; node(int a=0,int b=0,double r=0,double d=0):a(a),b(b),r(r),d(d) {} bool operator < (const node& rhs) const { return r < rhs.r; } }a[maxn*maxn]; struct hehe { int a; double d; hehe(int a=0, double d=0):a(a), d(d) {} bool operator < (const hehe& rhs) const { return d > rhs.d; } }; vector<node> g[maxn]; int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); } void print(int root) { vector<int> ans; while(root != S) { ans.push_back(root); root = path[root]; } ans.push_back(S); int len = ans.size(); for(int i=len-1;i>=0;i--) { if(i == len-1) printf("%d",ans[i]); else printf(" %d",ans[i]); } printf("\n%.1f %.1f\n",d[T],ans_t); } void dij() { priority_queue<hehe> q; for(int i=1;i<=n;i++) d[i] = INF, done[i] = false; d[S] = 0; q.push(hehe(S,0)); while(!q.empty()) { hehe u = q.top(); q.pop(); if(done[u.a]) continue; done[u.a] = true; int len = g[u.a].size(); for(int i=0;i<len;i++) { node v = g[u.a][i]; if(d[v.a] > d[u.a] + v.d && fabs(d[v.a]-d[u.a]-v.d) > eps) { d[v.a] = d[u.a] + v.d; path[v.a] = u.a; q.push(hehe(v.a,d[v.a])); } } } print(T); } void solve() { sort(a, a+m); for(int i=1;i<=n;i++) p[i] = i, g[i].clear(); ans_t = 0.0; memset(vis, false, sizeof(vis)); for(int i=0;i<m;i++) { int x = _find(a[i].a), y = _find(a[i].b); if(x != y) { p[x] = y; vis[i] = true; g[a[i].a].push_back(node(a[i].b,0,a[i].r,a[i].d)); g[a[i].b].push_back(node(a[i].a,0,a[i].r,a[i].d)); x = _find(S); y = _find(T); ans_t = max(ans_t, a[i].r); if(x == y) break; } } for(int i=0;i<m;i++) { if(!vis[i] && (ans_t > a[i].r || fabs(a[i].r-ans_t) < eps)) { g[a[i].a].push_back(node(a[i].b,0,a[i].r,a[i].d)); g[a[i].b].push_back(node(a[i].a,0,a[i].r,a[i].d)); } } dij(); } int main() { while(~scanf("%d%d",&n,&m)) { scanf("%d%d",&S,&T); for(int i=0;i<m;i++) scanf("%d%d%lf%lf",&a[i].a,&a[i].b,&a[i].r,&a[i].d); solve(); } return 0; }
UVA 10816 - Travel in Desert(最小生成树+最短路)
原文:http://blog.csdn.net/weizhuwyzc000/article/details/50674893