计蒜客简单图论（并查集 + 排序 + 枚举）

冷不防 2024-02-17 22:06 69阅读 0赞

一个无向图有n个点和m条边，每条边有权值。两点间的路径权值为这条路径上的最大边权和最小边权的比值。

给定一个起点和一个终点，问从起点到终点的路径中，权值最小的比值是多少。

如果起点和终点无法联通，则输出“No Answer”（结果不带引号）。

输出的比值结果严格保留两位小数。

输入第一行为两个整数，n（1<n≤500）和m（1≤m≤5000）表示图中点的数量和双向边的数量。接下来每行3个整数x，y（1≤x，y≤n），p（0<p<30000）表示点x和点y之间有一条双向边，权值为p。第m+1行为两个整数s，t（1≤s，t≤n， s不等于t），表示起点和终点。

输出仅一个数，表示最小的比值，结果保留两位小数。

##### 样例输入 #####

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

##### 样例输出 #####

1.25

分析：数据量最大为5000，先排序，再枚举边 + 并查集

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    #include<algorithm>
    #define INF 100000000
    const int maxn=5000+10;
    int u[maxn],v[maxn],r[maxn],w[maxn];  //r存储边的序号 
    int pre[500+10];
    int n,m;
    
    bool cmp(int i,int j){
    	return w[i]<w[j];
    }
    
    int find(int x){
    	return x==pre[x]?x:find(pre[x]);
    }
    
    void init(){
    	for(int i=1;i<=n;i++)
    	pre[i]=i;
    }
    
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=1;i<=m;i++){
    			scanf("%d%d%d",&u[i],&v[i],&w[i]);
    			r[i]=i;
    		}
    		
    		int s,t;
    		scanf("%d%d",&s,&t);
    		
            sort(r+1,r+m+1,cmp);
            double ans = (double)INF;
            int flag=1;
            
            for(int i=1;i<=m;i++){
            	init();
            	int j;
            	for(j=i;j<=m;j++){
            		int x=u[r[j]],y=v[r[j]];
            		int fa=find(x),fb=find(y);
            		
            		if(fa!=fb){
            			pre[fa]=fb;
    				}
    				if(find(s)==find(t)){
    					break;
    				}
    			}
    			
    			if(find(s)!=find(t)){
    				if(i==1){
    					printf("No Answer\n");
    					flag=0;
    					break ;
    				}
    				else break;
    			}
    			
    			if(ans>(double)w[r[j]]/w[r[i]]){
    				ans=(double)w[r[j]]/w[r[i]];
    			}
    		}
    		
    		if(flag)printf("%.2lf\n",ans);
    	}
    	return 0;
    }