当前位置:编程学习 > C/C++ >>

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++; 
            } 
          
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,