第六届河南省程序设计大赛——C 最舒适的路线（并查集）

「爱情、让人受尽委屈。」 2022-04-25 03:14 103阅读 0赞

## 题目描述: ##

异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,…,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。

现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。

## 输入描述: ##

<span style="color:#000000">第一行： K     表示有多少组测试数据。 
    接下来对每组测试数据：
    第1行:       N  M
    第2~M+1行： Xi  Yi  Vi   (i=1,…..,M)
    表示神经元Xi 到神经元Yi之间通道的速度必须是Vi
    最后一行：     S  T     ( S  T )
    
    【约束条件】
     2≤K≤5   1<N≤500   0<M≤5000   1≤ Xi, Yi , S , T ≤N   0< Vi <30000，
    Vi是整数。数据之间有一个空格。
    </span>

## 输出描述: ##

<span style="color:#000000">对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。</span>

## 样例输入: ##

复制

2
    3 2
    1 2 2
    2 3 4
    1 3
    3 3
    1 2 10
    1 2 5
    2 3 8
    1 3

## 样例输出: ##

2
    5/4

## 首先这一题使用dfs是够呛，第一时间不够，第二有重边dfs的话不好处理，最好还是使用并查集判断s和t是否在一个团伙里，在的话就说明能够到达 ##

## 解题的中心思想是使用并查集判断两个边能否 ##

## 1，将所有的边按照从大到小顺序排序， ##

## 2，从当前最大边开始，依次放入边，直至s和t在一个团伙中，记录下这些边中的最大值和最小值 ##

## 3，将最大边抛弃，重复2的操作 ##

## 4，重复操作2直至将剩余所有边放入都无法使s和t在一个团伙里 、退出 ##

## 5，将上面重复2操作时出现的所有（最大值最小值）对、进行挨个比较找到比值最小的 ##

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int k,book[505];   //book数组用来标记各个顶点头目，以此实现并查集 
    typedef struct cord{   //结构体包含 边的出发点、到达点、边的值 
    	int x,y,v;
    }cord;
    bool cmp(cord c1,cord c2){   //以边的值为准从小到大排序 
    	return c1.v>c2.v;
    }
    int seek(int x){     //找到x的团伙头目 
    	while(book[x]!=x){
    		x=book[x];
    	}
    	return x;
    }
    int zuida(int a,int b){   //找到整数ab的最大公约数 
    	if(b==0)return a;
    	else zuida(b,a%b);
    }
    int main(){
    	cin>>k;
    	while(k--){
    		int n,m,s,t;
    		cin>>n>>m;
    		cord c[5005];
    		for(int i=0;i<m;i++){
    			scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].v);
    		}
    		cin>>s>>t;
    		sort(c,c+m,cmp);   //排序 
    		int goodmin=1,goodmax=300000,min1=300000,max1=0;  //goodmin以及goodmax是代表最终的解，min1和max1是代表每一次成功使s和t是同一头目时出现的最大值最小值 
    		int i=0,i1=0;   //i用来循环，i1=0时代表从0到m的边都可以用，i1=3时代表从3到m之间的边才可以用，0,1,2这三条边已经被舍弃了 
    		bool flag=false,flag1=false;                  //flag的值代表s到t之间是否有解   flag1的值代表每一轮循环s到t是否有解 
    		while(i<m){
    			min1=300000;max1=0;   //每轮循环前都要初始化关键数据 
    		    i=i1++;
    		    flag1=false; 
    			for(int j=1;j<=n;j++){   //每轮循环尝试前，必须将每个顶点的头目设置为自己 
    			    book[j]=j;
    		    }
    		    while(seek(s)!=seek(t)&&i<m){    //若s和t还不是同一个头目，则持续加边，直至s和t是同一个头目， 
    		    	if(seek(c[i].x)!=seek(c[i].y)){    //如果边的两头还不在一个团伙中，则将其归并到一起 
    		    		book[seek(c[i].x)]=seek(c[i].y);
    				}
    		    	min1=min(min1,c[i].v);    //更新此轮出现的最大值最小值 
    		    	max1=max(max1,c[i].v);
    		    	i++;
    		    } 
    		    if(seek(s)==seek(t)){  //由于上面的while循环也可能是i>=n跳出的循环，所以需要判断一下是否是已经是s和t是同一个团伙 
    		    	flag=true;           //如果是，则将两个标记都设为true 
    		    	flag1=true;
    		    }
    		    if(i>=m&&!flag1)break;  //如果此时是i>=n跳出的循环且并没有使s和t在同一个团伙内，则说明剩下的所有边已经不可能有解了 
    		    if(flag1){    //如果此轮循环有解，则判断是否更新最终输出的解 
    		    	double t1=(double)goodmax/goodmin,t2=(double)max1/min1;
    		        if(t1>t2){
    		    	    goodmax=max1;
    		    	    goodmin=min1;
    		        }
    		    }
    		}
    		if(!flag){      //无解的情况 
    			cout<<"IMPOSSIBLE"<<endl;
    			continue;
    		}
    		int num=zuida(goodmax,goodmin);   //获取最大公约数 
    		if(num==goodmin)cout<<goodmax/goodmin<<endl;   //是整数的情况 
    		else cout<<goodmax/num<<"/"<<goodmin/num<<endl; 
    	} 
    	return 0;
    }