首页 > 代码库 > HDU 1598 find the most comfortable road

HDU 1598 find the most comfortable road

2024-07-13 04:22:21   212人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题意：中文题

题解：枚举+最小生成树(Kruskal)。对于每个要查询的s，e，枚举边。总是忘记minn初始化……

  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 const int maxn=2010; 23  24 int N,M; 25 int V,E; 26  27 int par[maxn]; 28 int rankh[maxn]; 29 struct edge{ 30     int u,v,cost; 31 }; 32 edge es[maxn]; 33  34 bool cmp(const edge& e1,const edge& e2) 35 { 36     return e1.cost<e2.cost; 37 } 38  39 void init(int n) 40 { 41     for(int i=0;i<=n;i++) 42     { 43         par[i]=i; 44         rankh[i]=0; 45     } 46 } 47  48 int find(int x) 49 { 50     if(par[x]==x) 51     { 52         return x; 53     } 54     else{ 55         return par[x]=find(par[x]); 56     } 57 } 58  59 /*int find(int x) 60 { 61     while(x!=par[x]) x=par[x]; 62     return x; 63 }*/ 64  65 void unite(int x,int y) 66 { 67     x=find(x); 68     y=find(y); 69     if(x==y) return; 70     if(rankh[x]<rankh[y]){ 71         par[x]=y; 72     } 73     else{ 74         par[y]=x; 75         if(rankh[x]==rankh[y]) rankh[x]++; 76     } 77 } 78  79 bool same(int x,int y) 80 { 81     return find(x)==find(y); 82 } 83  84 int main() 85 { 86     //freopen("/Users/apple/Desktop/暑假/10/10/in","r",stdin); 87     while(scanf("%d%d",&N,&M)!=EOF) 88     { 89         V=N; 90         E=M; 91         int minn; 92         for(int i=0;i<M;i++) 93         { 94             scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost); 95             // printf("%d %d %d \n",es[i].u,es[i].v,es[i].cost); 96         } 97         //   puts("asdfghjkl"); 98         sort(es,es+E,cmp); 99         //   for(int i=0;i<M;i++)100         //   {101         //       printf("%d %d %d \n",es[i].u,es[i].v,es[i].cost);102         //   }103         int Q;104         scanf("%d",&Q);105         while(Q--)106         {107             int s,e;108             scanf("%d%d",&s,&e);109             minn=INF;110             for(int i=0;i<E;i++)111             {112                 init(V);113                 for(int j=i;j<E;j++)114                 {115                     int a=find(es[j].u);116                     int b=find(es[j].v);117                     if(a!=b) unite(a,b);118                     if(find(s)==find(e))119                     {120                         minn=min(minn,es[j].cost-es[i].cost);121                         //printf("%d ",minn);122                         break;123                     }124                 }125             }126             if(minn==INF) puts("-1");127             else printf("%d\n",minn);128             //puts("");129         }130 131     }132     133     return 0;134 }


联系
我们