网站开发项目经验,用ps做网站设计,深圳电梯广告制作公司网站,口碑好的宜昌网站建设【题意】 有n个绿洲#xff0c; m条道路#xff0c;每条路上有一个温度#xff0c;和一个路程长度#xff0c;从绿洲s到绿洲t#xff0c;求一条道路的最高温度尽量小#xff0c; 如果有多条#xff0c; 选一条总路程最短的。 InputInput consists of several test cases… 【题意】 有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 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 #includequeue7 #includecmath8 using namespace std;9 #define Maxn 11010 #define Maxm 1001011 #define INF 0xfffffff12 13 int n,m,st,ed;14 15 struct node16 {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.cy.c;}23 // double mymax(double x,double y) {return xy?x:y;}24 int mymax(int x,int y) {return xy?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].xx;t[len].yy;t[len].cc;36 t[len].nextfirst[x];first[x]len;37 }38 39 int mx[Maxn];40 void dfs(int x,int f)41 {42 for(int ifirst[x];i;it[i].next) if(t[i].y!f)43 {44 int yt[i].y;45 mx[y]mymax(mx[x],t[i].c);46 dfs(y,x);47 }48 }49 50 queueint q;51 int pre[Maxn],dis[Maxn];52 bool inq[Maxn];53 void spfa()54 {55 while(!q.empty()) q.pop();56 // for(int i1;in;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 xq.front();63 for(int ifirst[x];i;it[i].next)64 {65 int yt[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 nowst;81 while(now!ed)82 {83 printf(%d ,now);84 nowpre[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 i1;im;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(tt1,tt1m,cmp);
102 for(int i1;in;i) fa[i]i;
103 int cnt0;
104 memset(first,0,sizeof(first));
105 len0;
106 for(int i1;im;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(cntn-1) break;
116 }
117 mx[ed]0;
118 dfs(ed,0);
119 len0;
120 memset(first,0,sizeof(first));
121 for(int i1;im;i) if(tt[i].cmx[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
