首页 > 代码库 > lightoj 1002 最小生成树
lightoj 1002 最小生成树
题意，给出若干条道路(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 最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。