首页 > 代码库 > 舒适的旅行(并查集)
舒适的旅行(并查集)
1050: [HAOI2006]旅行comf
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3107 Solved: 1701
[Submit][Status][Discuss]
Description
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出
这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
Input
第一行包含两个正整数，N和M。下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向
公路，车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速
度比最小的路径。s和t不可能相同。
1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000
Output
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一
个既约分数。
Sample Input
【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3
Sample Output
【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
//很稳。。。根本不是搜索题，用搜索做肯定超时，做法是用并查集加个M^2的算法做
将边按权值排好序后，枚举边，依次将之作为最小边，再一重循环一直加入进来，直到s，t连通，那这条边一定是最大边
1 #include <stdio.h> 2 #include <iostream> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 7 #define MAXM 5005 8 #define INF 500000000 9 typedef long long LL;10 11 int n,m;12 int s,t;13 int f[505];14 struct Bian15 {16 int from;17 int to;18 int v;19 bool operator < (const Bian b) const20 {return v<b.v;}21 }G[MAXM];22 23 int gcd(int a,int b)24 {25 return b==0?a:gcd(b,(a%b));26 }27 28 void Init_Bin()29 {30 for (int i=1;i<=n;i++)31 f[i]=i;32 }33 34 int find_h(int x)35 {36 if (x!=f[x])37 f[x]=find_h(f[x]);38 return f[x];39 }40 41 42 int main()43 {44 while (scanf("%d%d",&n,&m)!=EOF)45 {46 for (int i=0;i<m;i++)47 {48 int x,y,v;49 scanf("%d%d%d",&x,&y,&v);50 G[i]=(Bian){x,y,v};51 }52 sort(G,G+m);53 scanf("%d%d",&s,&t);54 int ansx=INF,ansy=-INF;55 double res=INF;56 for (int i=0;i<m;i++)57 {58 if (i>0&&G[i].v==G[i-1].v) continue;//剪枝,减很久时间59 Init_Bin(); //初始化并查集60 int low =G[i].v,high;61 for (int j=i;j<m;j++)62 {63 int fx=find_h(G[j].from),fy=find_h(G[j].to);64 if (fx!=fy)65 f[fx]=f[fy];66 high=G[j].v;67 if (find_h(s)==find_h(t))68 {69 double kk=(double)high/low;70 if (kk<res)71 {72 res=kk;73 ansx=high;74 ansy=low;75 }76 break;77 }78 }79 }80 if (res==INF)81 printf("IMPOSSIBLE\n");82 else83 {84 int yue=gcd(ansx,ansy);85 if (ansy/yue==1)86 printf("%d\n",ansx/yue);87 else88 printf("%d/%d\n",ansx/yue,ansy/yue);89 }90 }91 return 0;92 }
舒适的旅行(并查集)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。