【题意】
有n个绿洲， m条道路，每条路上有一个温度，和一个路程长度，从绿洲s到绿洲t，求一条道路的最高温度尽量小， 如果有多条， 选一条总路程最短的。
InputInput consists of several test cases. Your program must process all of them.The first line contains two integers N and E (1 ≤ N ≤ 100; 1 ≤ E ≤ 10000) where N represents thenumber of oasis and E represents the number of paths between them. Next line contains two distinctintegers S and T (1 ≤ S, T ≤ N) representing the starting point and the destination respectively. Thefollowing E lines are the information the group gathered. Each line contains 2 integers X, Y and 2 realnumbers R and D (1 ≤ X, Y ≤ N; 20 ≤ R ≤ 50; 0 < D ≤ 40). It means there is a path between X andY , with length D km and highest temperature RoC. Each real number has exactly one digit after thedecimal point. There might be more than one path between a pair of oases.OutputPrint two lines for each test case. The first line should give the route you find, and the second shouldcontain its length and maximum temperature.Sample Input6 91 61 2 37.1 10.22 3 40.5 20.73 4 42.8 19.03 1 38.3 15.84 5 39.7 11.16 3 36.0 22.55 6 43.9 10.22 6 44.2 15.24 6 34.2 17.4Sample Output1 3 638.3 38.3
【分析】
我们可以先求出最大温度的最小值，然后把小于等于这个温度的边加进图中跑最短路。
最短路就不说了，现在就是要求最小瓶颈路。
最小瓶颈路有两个方法，
1、二分+BFS
二分之后沿着小于等于这个温度的边走，只需判断能否走到终点，所以是mlogn的。
2、
但其实可以nlogn把图上所有两点的最小瓶颈路求出来，就是求出最小瓶颈树，那么两点之间的唯一路径就是他们的最小瓶颈路。
而最小生成树就是一个最小瓶颈树。
[其实这个，我也不是很会证明的说- -谁能告诉我- -]
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define Maxn 110 10 #define Maxm 10010 11 #define INF 0xfffffff 12 13 int n,m,st,ed; 14 15 struct node 16 { 17 int x,y,c,d; 18 int next; 19 }tt[Maxm],t[Maxm*2]; 20 int len,first[Maxn]; 21 22 bool cmp(node x,node y) {return x.c<y.c;} 23 // double mymax(double x,double y) {return x>y?x:y;} 24 int mymax(int x,int y) {return x>y?x:y;} 25 26 int fa[Maxn]; 27 int ffa(int x) 28 { 29 if(fa[x]!=x) fa[x]=ffa(fa[x]); 30 return fa[x]; 31 } 32 33 void ins(int x,int y,int c) 34 { 35 t[++len].x=x;t[len].y=y;t[len].c=c; 36 t[len].next=first[x];first[x]=len; 37 } 38 39 int mx[Maxn]; 40 void dfs(int x,int f) 41 { 42 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f) 43 { 44 int y=t[i].y; 45 mx[y]=mymax(mx[x],t[i].c); 46 dfs(y,x); 47 } 48 } 49 50 queue<int > q; 51 int pre[Maxn],dis[Maxn]; 52 bool inq[Maxn]; 53 void spfa() 54 { 55 while(!q.empty()) q.pop(); 56 // for(int i=1;i<=n;i++) dis[i]=INF; 57 memset(dis,63,sizeof(dis)); 58 memset(inq,0,sizeof(inq)); 59 q.push(ed);inq[ed]=1;dis[ed]=0; 60 while(!q.empty()) 61 { 62 int x=q.front(); 63 for(int i=first[x];i;i=t[i].next) 64 { 65 int y=t[i].y; 66 if(dis[y]>dis[x]+t[i].c) 67 { 68 dis[y]=dis[x]+t[i].c; 69 pre[y]=x; 70 if(!inq[y]) 71 { 72 q.push(y); 73 inq[y]=1; 74 } 75 } 76 } 77 inq[x]=0;q.pop(); 78 } 79 if(dis[st]>=INF-10000) return; 80 int now=st; 81 while(now!=ed) 82 { 83 printf("%d ",now); 84 now=pre[now]; 85 } 86 printf("%d\n",ed); 87 printf("%.1lf %.1lf\n",dis[st]*1.0/10,mx[st]*1.0/10); 88 } 89 90 int main() 91 { 92 while(scanf("%d%d",&n,&m)!=EOF) 93 { 94 scanf("%d%d",&st,&ed); 95 for(int i=1;i<=m;i++) 96 { 97 double c,d; 98 scanf("%d%d%lf%lf",&tt[i].x,&tt[i].y,&c,&d); 99 tt[i].c=(int)round(c*10);tt[i].d=(int)round(d*10);100 }101 sort(tt+1,tt+1+m,cmp);102 for(int i=1;i<=n;i++) fa[i]=i;103 int cnt=0;104 memset(first,0,sizeof(first));105 len=0;106 for(int i=1;i<=m;i++)107 {108 if(ffa(tt[i].x)!=ffa(tt[i].y))109 {110 fa[ffa(tt[i].x)]=ffa(tt[i].y);111 cnt++;112 ins(tt[i].x,tt[i].y,tt[i].c);113 ins(tt[i].y,tt[i].x,tt[i].c);114 }115 if(cnt==n-1) break;116 }117 mx[ed]=0;118 dfs(ed,0);119 len=0;120 memset(first,0,sizeof(first));121 for(int i=1;i<=m;i++) if(tt[i].c<=mx[st])122 {123 ins(tt[i].x,tt[i].y,tt[i].d);124 ins(tt[i].y,tt[i].x,tt[i].d);125 }126 spfa();127 }128 return 0; 129 } View Code
2016-11-01 15:57:34
转载于:https://www.cnblogs.com/Konjakmoyu/p/6019717.html
