uva 10099(最大生成树+搜索)

题意：给一个源点一个终点求一条路径是路径上最小的那条边最大。
思路：先求最大生成树，然后从源点搜索到终点求权值最小的边即可。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <stack>
 10 #define INF 0x7fffffff
 11 #define eps 1E-8
 12 #define LEN 110
 13 
 14 using namespace std;
 15 
 16 int n, m, top, vis[LEN*LEN], CC = 1;
 17 
 18 struct Edge{
 19     int a, b, val;
 20     void make_edge(int _a, int _b, int _v){
 21         a = _a, b = _b; val = _v;
 22     }
 23 }edge[LEN*LEN];
 24 bool cmp(Edge a, Edge b){return a.val>b.val;}
 25 
 26 //UFSet
 27 int parent[LEN];
 28 
 29 void init(){for(int i=0; i<LEN; i++)parent[i] = i;}
 30 int Find(int x){return parent[x]==x?x:Find(parent[x]);}
 31 void Union(int a, int b){int pa=Find(a), pb=Find(b);if(pa!=pb)parent[pa]=pb;}
 32 
 33 //kruskal
 34 int Kruskal()
 35 {
 36     memset(vis, 0 ,sizeof vis);
 37     init();
 38     int cnt = 0, ret = 0;;
 39     for(int i=0; i<top; i++){
 40         if(Find(edge[i].a)!=Find(edge[i].b)){
 41             cnt++;
 42             Union(edge[i].a, edge[i].b);
 43             ret+=edge[i].val;
 44             vis[i] = 1;
 45         }
 46         if(cnt==n-1)break;
 47     }
 48     return ret;
 49 }
 50 
 51 int dfs(int st, int en)
 52 {
 53     int v[LEN];
 54     for(int i=0; i<LEN; i++){
 55         v[i] = INF;
 56     }
 57     queue<int> q;
 58     q.push(st);
 59     v[st] = INF-1;
 60     while(!q.empty()){
 61         int vex = q.front();q.pop();
 62         if(vex == en){return v[en];}
 63         for(int i=0; i<top; i++){
 64             if(vis[i] && edge[i].a==vex && v[edge[i].b] == INF){
 65                 q.push(edge[i].b);
 66                 v[edge[i].b] = min(v[edge[i].a], edge[i].val);
 67             }
 68             if(vis[i] && edge[i].b==vex && v[edge[i].a] == INF){
 69                 q.push(edge[i].a);
 70                 v[edge[i].a] = min(v[edge[i].b], edge[i].val);
 71             }
 72         }
 73     }
 74     return -1;
 75 }
 76 
 77 int main()
 78 {
 79 //    freopen("in.txt", "r", stdin);
 80 
 81     while(scanf("%d%d", &n, &m)!=EOF){
 82         if(!n && !m) break;
 83         top = 0;
 84         int a, b, v;
 85         for(int i=0; i<m; i++){
 86             scanf("%d%d%d", &a, &b, &v);
 87             edge[top++].make_edge(a, b, v);
 88         }
 89         int st, en, num;
 90         scanf("%d%d%d", &st, &en, &num);
 91         sort(edge, edge+top, cmp);
 92         Kruskal();
 93         int ans = dfs(st, en) - 1;
 94         int aa = num/ans;
 95         if(num%ans!=0)aa++;
 96         printf("Scenario #%d
", CC++);
 97         printf("Minimum Number of Trips = %d

", aa);
 98     }
 99     return 0;
100 }
View Code
奔跑吧！少年！趁着你还年轻