uva 10099 - The Tourist Guide(最小生成树）

解题思路：这题因为以前做过一遍，所以知道有个坑点，就是导游每次必须跟团。我是用kruskal算法去做的，因为题目只要求说运输的次数最少，没有说要求路径的长度，所以每次从最长的边开始加入，直道起点与终点相连接，那么最后加入的那条边就是整条路的限制人数，然后算运输次数时注意导游每次要跟队就可以了。

#include   
#include   
#include   
using namespace std;  
const int N = 105;  
struct state {  
    int r, l, num;  
}s[N * N];  
int n, m, ans, begin, end, sum, f[N];  
  
int getfather(int x) {  
    return x == f[x]   x : f[x] = getfather(f[x]);  
}  
  
bool cmp(const state& a, const state& b) {  
    return a.num > b.num;  
}  
  
void init() {  
    for (int i = 0; i < m; i++)  
        scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].num);  
    scanf("%d%d%d", &begin, &end, &sum);  
    for (int i = 1; i <= n; i++)  
        f[i] = i;  
    sort(s, s + m, cmp);  
}  
  
int kruskal() {  
    for (int i = 0; i < m; i++) {  
        int p = getfather(s[i].l), q = getfather(s[i].r);  
        if (p != q) {  
            f[p] = q;  
            if (getfather(begin) == getfather(end))  
                return s[i].num;  
        }  
    }  
    return 0;  
}  
  
int solve() {  
    if (sum % ans)  
        return sum / (ans - 1) + 1;  
    else  
        return sum / (ans - 1);  
}  
  
int main () {  
    int cas = 1;  
    while (scanf("%d%d", &n, &m), n || m ) {  
        init();  
        ans = kruskal();  
        printf("Scenario #%d\n", cas++);  
        printf("Minimum Number of Trips = %d\n\n", solve());  
    }  
    return 0;  
}