【UVA 10816】 Travel in Desert （最小瓶頸樹+最短路）

【題意】

　　有n個綠洲， m條道路，每條路上有一個溫度，和一個路程長度，從綠洲s到綠洲t，求一條道路的最高溫度盡量小，如果有多條，選一條總路程最短的。

Input
Input 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 the
number of oasis and E represents the number of paths between them. Next line contains two distinct
integers S and T (1 ≤ S, T ≤ N) representing the starting point and the destination respectively. The
following E lines are the information the group gathered. Each line contains 2 integers X, Y and 2 real
numbers R and D (1 ≤ X, Y ≤ N; 20 ≤ R ≤ 50; 0 < D ≤ 40). It means there is a path between X and
Y , with length D km and highest temperature RoC. Each real number has exactly one digit after the
decimal point. There might be more than one path between a pair of oases.
Output
Print two lines for each test case. The first line should give the route you find, and the second should
contain its length and maximum temperature.
Sample Input
6 9
1 6
1 2 37.1 10.2
2 3 40.5 20.7
3 4 42.8 19.0
3 1 38.3 15.8
4 5 39.7 11.1
6 3 36.0 22.5
5 6 43.9 10.2
2 6 44.2 15.2
4 6 34.2 17.4
Sample Output
1 3 6
38.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

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/373590.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/373590.shtml
英文地址，請注明出處：http://en.pswp.cn/news/373590.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！