The Tourist Guide

The Tourist Guide

一开始用搜索，超时。

大神说最小生成树，krustal算法，边排序以后，从小到大一条条检查，如果理解的两个点属于两个连通分支，那么这条边就归入边集。

这里需要找到所有路径最小边中的最大值，那么就从大到小，一条条检查是不是这条边：对于某边，取大于它的边，连接点，看最后起始点和终点是否连通

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct Edge{
int u,v,r;
}e[10000];
int root[110];
int set_find(int x){return root[x]==x?x:(root[x]=set_find(root[x]));}
void set1_union(int a,int b){
int ra=set_find(a);
int rb=set_find(b);
if(ra!=rb){
    root[ra]=rb;
}
}
bool cmp(Edge a,Edge b){
return a.r>b.r;
}
int main(){
int T=1;
int N,R;
while((cin>>N>>R)&&(N||R)){
    int cnt=0;
    while(R--){
        Edge&t=e[cnt];
        cin>>t.u>>t.v>>t.r;
        cnt++;
    }
    R=cnt;
    sort(e,e+R,cmp);
    int x,y,t;
    cin>>x>>y>>t;
    for(int j=1;j<=N;j++)root[j]=j;
    int i;
    for(i=0;i<R;i++){
        for(int j=i;j>=0;j--)
            set1_union(e[j].u,e[j].v);
        if(set_find(x)==set_find(y))break;
    }
    int m=e[i].r;
    cout<<"Scenario #"<<T++<<endl;
    cout<<"Minimum Number of Trips = "<<t/(m-1)+(t%m?1:0)<<endl<<endl;
}
return 0;}