POJ2263&&1797 最大生成樹

兩題都是求最大生成樹中的最小值。當找到起點與終點的時候退出。
沒什麼陷阱，直接貼代碼。
1797
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define Max 100000 
#define inf 1<<28 
using namespace std; 
struct kdq 
{ 
    int s,e,l; 
} line[Max]; 
int n,m; 
int f[Max*10]; 
int find(int x) 
{ 
    return f[x]==x?x:f[x]=find(f[x]); 
} 
void merge(int x,int y) 
{ 
    if(x>y) 
        f[x]=y; 
    else 
        f[y]=x; 
} 
bool cmp(kdq &a,kdq &b) 
{ 
    return a.l>b.l; 
} 
int kruskal() 
{ 
    int i,j; 
    for(i=1; i<=n+10; i++) 
        f[i]=i; 
    int ans=inf; 
    for(i=0; i<m; i++) 
    { 
        int x=find(line[i].s); 
        int y=find(line[i].e); 
        if(x!=y) 
        { 
            merge(x,y); 
            if(ans>line[i].l) 
                ans=line[i].l; 
            if(find(1)==find(n)) 
                return ans; 
        } 
    } 
} 
int main() 
{ 
    int i,j,k=0,l; 
    int T; 
    cin>>T; 
    int x,y,s; 
    while(T--) 
    { 
        k++; 
        cin>>n>>m; 
        for(i=0; i<m; i++) 
        { 
            scanf("%d%d%d",&line[i].s,&line[i].e,&line[i].l); 
        } 
        sort(line,line+m,cmp); 
        printf("Scenario #%d:\n",k); 
        cout<<kruskal()<<endl<<endl; 
    } 
    return 0; 
} 
/*
1
4 2
1 3 1
3 4 2
*/ 
2263
[cpp]
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define PI acos(-1.0) 
#define Max 20005 
#define inf 1<<28 
#define LL(x) (x<<1) 
#define RR(x)(x<<1|1) 
using namespace std; 
 
int n,m; 
struct kdq 
{ 
    int s,e,l; 
} line[Max]; 
 
bool cmp(kdq &a,kdq &b) 
{ 
    return a.l>b.l; 
} 
int f[Max]; 
void init() 
{ 
    for(int i=0; i<=n; i++) 
        f[i]=i; 
} 
int find(int x) 
{ 
    return f[x]==x?x:f[x]=find(f[x]); 
} 
void Union(int x,int y) 
{ 
    x=find(x); 
    y=find(y); 
    if(x==y)return ; 
    if(x>y) 
        f[x]=y; 
    else 
        f[y]=x; 
} 
int kruskal(int s,int e,int num) 
{ 
    init(); 
    int ans=inf; 
    for(int i=0; i<num; i++) 
    { 
        int x=find(line[i].s); 
        int y=find(line[i].e); 
        if(x!=y) 
        { 
            Union(x,y); 
            if(ans>line[i].l) 
                ans=line[i].l; 
            if(find(s)==find(e)) 
                return ans; 
        } 
    } 
} 
int main() 
{ 
    int i,j,k,l; 
    int cc=0; 
    char aaaa[40],bbbb[40]; 
    while(scanf("%d%d",&n,&m),(n+m)) 
    { 
        map<string,int>mymap; 
        string a,b; 
        int num=1; 
        int num1=0; 
        while(m--) 
        { 
            scanf("%s%s%d",aaaa,bbbb,&l); 
            a=aaaa,b=bbbb; 
            if(!mymap[a]) 
            { 
                mymap[a]=num; 
                num++; 
            } 
            if(!mymap[b]) 
            { 
                mymap[b]=num; 
                num++; 
            } 
            line[num1].s=mymap[a],line[num1].e=mymap[b],line[num1].l=l; 
            num1++; 
        } 
        sort(line,line+num1,cmp); 
        scanf("%s%s",aaaa,bbbb); 
        a=aaaa,b=bbbb; 
        printf("Scenario #%d\n%d tons\n\n",++cc,kruskal(mymap[a],mymap[b],num1)); 
    } 
    return 0; 
}