题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1050
思路:
先将每条边的权值排个序优先小的, 然后从小到大枚举每一条边, 将其存到并查集里, 如果得到的比值比之前的小, 那么判断下 s 与 t 能否连通, 如果连通就替换就好了
实现代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int M = 1e6+10;
- int f[M],vis[M],a[M];
- int n,m;
- int Find(int x){
- if(x==f[x])return x;
- return f[x]=Find(f[x]);
- }
- void mix(int x,int y){
- int fx = Find(x);
- int fy = Find(y);
- if(fx != fy) f[fx] = fy;
- }
- bool cmp(int a,int b){
- return a> b;
- }
- struct node{
- int x,y,v;
- bool operator <(const node &cmp) const{
- return v < cmp.v;
- }
- }e[M];
- int main()
- {
- int s,t;
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= m;i ++)
- scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
- sort(e+1,e+1+m);
- scanf("%d%d",&s,&t);
- int minn = 1,maxx = 30000;
- for(int i = 1;i <= m;i ++){
- for(int j = 1;j <= n;j ++) f[j] = j;
- for(int j = i;j <= m;j ++){
- mix(e[j].x,e[j].y);
- if(e[j].v*minn> e[i].v*maxx) break;
- if(Find(s) == Find(t)){
- int k = __gcd(e[j].v,e[i].v);
- minn = e[i].v/k; maxx = e[j].v/k;
- // cout<<k<<""<<minn<<" "<<maxx<<endl;
- break;
- }
- }
- }
- if(maxx == 30000&&minn == 1) printf("IMPOSSIBLE\n");
- else if(minn == 1) printf("%d\n",maxx);
- else cout<<maxx<<"/"<<minn<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2694169.html