首页 > 代码库 > lightoj 1002 最小生成树

lightoj 1002 最小生成树

2024-08-16 01:23:16   212人阅读

题意，给出若干条道路(m条)和若干个城市(n个，编号从0~n-1)，给出一个起步城市k( 0<=k<=n) , 问所有其他城市到起步城市k的路径中，路径中最长的道路，最短可以 是多少。

 

分析，虽然一开始看错了题目，当作了最短路做，改了回来，用了并查集＋队列拓展。但是Gealo说可以用dij做，数组保存的不是到某点的最短距离，而是到某点的最长的道路长为多少。好像也是可以的。

总之写的是最小生成树，那就用最小生成树写，最小生成树可以完美保证题意，题意中要找到路径，也就是要联通，且最小，符合最小生成树定义。

 1 /* When all else is lost the future still remains. */ 2 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++) 3 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--) 4 #define fi first 5 #define se second 6 //head 7 #include <iostream> 8 #include <stdio.h> 9 #include <queue>10 #include <algorithm>11 using namespace std;12 #define MAXM 1601013 #define MAXN 51014 #define INF 100000000015 //int road_val[MAXN][MAXN];16 pair<int,pair<int,int> > road_val[MAXM];17 int dis[MAXN][MAXN];18 int fat[MAXN];19 int maxdis[MAXN];20 int dij_dis[MAXN];21 bool mark[MAXN];22 void init(){23     rep(i,0,MAXN) rep(j,0,MAXN) dis[i][j] = INF;24     rep(i,0,MAXN) fat[i] = i;25     rep(i,0,MAXN) dij_dis[i] = INF;26     rep(i,0,MAXN) maxdis[i] = -1;27     rep(i,0,MAXN) mark[i] = 0;28     return ;29 }30 int find_fa(int x){31     return fat[x] = (fat[x] == x) ? x : find_fa(fat[x]);32 }33 void dij(int pos , int n){34     queue<int> Q;35     Q.push(pos);36     maxdis[pos] = 0;37     while(!Q.empty()){38         int now = Q.front();39         Q.pop();40         mark[now] = 1;41         rep(i,0,n){42             if(mark[i]) continue;43             if(dis[now][i] >= INF) continue;44             maxdis[i] = max(maxdis[i],maxdis[now]);45             maxdis[i] = max(maxdis[i],dis[now][i]);46             Q.push(i);47         }48     }49     return ;50 }51 int main(){52     int T;53     scanf("%d",&T);54     rep(ca,1,T+1){55         int n , m;56         scanf("%d %d",&n,&m);57         init();58         rep(i,0,m){59             int u , v , w;60             scanf("%d %d %d",&u,&v,&w);61             road_val[i] = make_pair(w,make_pair(u,v));62         }63         sort(road_val,road_val+m);64         rep(i,0,m){65             int val = road_val[i].fi;66             int a = road_val[i].se.fi;67             int b = road_val[i].se.se;68             int fa = find_fa(a);69             int fb = find_fa(b);70             if(fa == fb) continue;71             fat[fa] = min(fa,fb);72             fat[fb] = min(fa,fb);73             dis[a][b] = min(dis[a][b],val);74             dis[b][a] = min(dis[b][a],val);75         }76         int start;77         scanf("%d",&start);78         dij(start,n);79         printf("Case %d:\n",ca);80         rep(i,0,n){81             if(maxdis[i] < 0) printf("Impossible\n");82             else printf("%d\n", maxdis[i]);83         }84 85     }86     return 0;87 }

 

lightoj 1002 最小生成树


联系
我们