首页 > 代码库 > Poj 3522 Slim Span

Poj 3522 Slim Span

2024-07-21 11:16:48   218人阅读

http://poj.org/problem?id=3522

题意：求最长边和最短边相差最小的最小生成树，输出差值，如果不可能输出-1。

题解：kruskal算法是对边进行升序排序后选取边进行构造最小生成树，所以利用kruskal，排序后，依次选取最开始的那一条边作为起始边进行构造，构造后将此边抛弃。对每一个生成树比较他　　　们的最大边和最小边的差值。

  1 #include <iostream>  2 #include <cstring>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cmath>  6 #include <string>  7 #include <vector>  8 #include <list>  9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <bitset> 13 #include <algorithm> 14 #include <numeric> 15 #include <functional> 16 #include <set> 17 #include <fstream> 18  19 using namespace std; 20  21 const int INF=0xfffffff; 22  23 const int maxv=110; 24 const int maxe=110*110; 25  26 int par[maxv],rankh[maxv]; 27 struct edge{ 28     int u,v,cost; 29 }; 30 edge es[maxe]; 31 int V,E; 32 int N,M; 33 int dif; 34  35 void init(int n) 36 { 37     for(int i=0;i<=n;i++) 38     { 39         par[i]=i; 40         rankh[i]=0; 41     } 42 } 43  44 int find(int x) 45 { 46     if(par[x]==x) return x; 47     else return par[x]=find(par[x]); 48 } 49  50 void unite(int x,int y) 51 { 52     x=find(x); 53     y=find(y); 54     if(x==y) return; 55     if(rankh[x]<rankh[y]){ 56         par[x]=y; 57         rankh[y]+=rankh[x]; 58     } else{ 59         par[y]=x; 60         rankh[x]+=rankh[y]; 61     } 62 } 63  64 bool same(int x,int y) 65 { 66     return find(x)==find(y); 67 } 68  69 bool cmp(const edge& e1,const edge& e2) 70 { 71     return e1.cost<e2.cost; 72 } 73  74 void kruskal() 75 { 76     dif=INF; 77     sort(es,es+E,cmp); 78     for(int i=0;i<E;i++) 79     { 80         init(V); 81         int cnt=0,tmp=INF; 82         for(int j=i;j<E;j++) 83         { 84             edge e=es[j]; 85             if(!same(e.u,e.v)){ 86                 unite(e.u,e.v); 87                 cnt++; 88                 if(cnt==V-1){ 89                     tmp=es[j].cost-es[i].cost; 90                     break; 91                 } 92             } 93         } 94         dif=min(dif,tmp); 95     } 96 } 97 int main() 98 { 99 //    freopen("/Users/apple/Desktop/暑假/POJ 3522/POJ 3522/in","r",stdin);100     while(scanf("%d%d",&N,&M)!=EOF)101     {102         if(N+M==0) break;103         V=N;104         E=M;105         for(int i=0;i<M;i++)106         {107             scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);108         }109         kruskal();110         if(dif==INF) puts("-1");111         else printf("%d\n",dif);112     }113     return 0;114 }

 

Poj 3522 Slim Span


联系
我们