【每日一题】1月15日题目精讲

题号 NC19963
名称 旅行
来源 [HAOI2006]
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者 YangYL°

前置知识

这道题的解法为：并查集 + 排序 + 二分

难度: 3 星

主要做法

首先考虑如何判断无解，很明显，无解的情况就是无论怎么样都不能从起点到终点，那么就是起点和终点在整个图中不连通，那么这种情况下输出"IMPOSSIBLE"，其余情况皆有解。

题目要求最大边与最小边的比值最小，所以我们不妨可以 枚举最小边 最大边，笔者选择的是枚举最小边。

因为此刻我们通过枚举已经确定的最小边，所以我们现在要最小化最大边。

在使用 的时候，加入的最后一条边就是整个生成树里面最大的一条边，在这道题里面最后加入的一条边的性质是什么呢？

不难想到加入的最后一条边一定是加入它之后使得终点和起点都联通了，这时候它就是最后一条边。

于是我们想到用同样的思路，先把边排序，然后从小到大枚举每一条边作为最小边的情况，然后不停的加边权大于等于它的边，倘若起点与终点已经联通，我们就停止加边，因为是 无向图，判断连通性用并查集即可。

然后用枚举到的最大边除以当前枚举到的最小边去更新答案，如果比答案更优，就记录下此时的最大边权和最小比权。

时间复杂度是：O( * 反阿克曼函数)。

如何比较两个分数的大小？

众所周知：假如 : 都大于

那么

所以得到:

是因为这里的边权较小，并不需要开，所以交叉相乘更方便。

对于此题的分析到此结束。

Code

#include <bits/stdc++.h>
using namespace std;

int n , m , cnt = 0,Ansa = 300001 ,Ansb = 1;//这个初值很讲究，不能爆int，也要恰好大于30000，于是就有了这个初值
int fa[505],s,t;

struct Edge {
    int from,to,w;
    bool operator < (const Edge& E) { return E.w > w;}
    void add(int u,int v, int W) { from = u , to = v , w = W; return ;}
} edge[10005];//双向边，记得开两倍空间

int find(int x) {
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];//路径压缩版的并查集
}

bool pd(int u,int v) {
    if(find(u) == find(v)) return 1;//判断u，v是否在同一个并查集中
    return 0;
}

void reset() {
    for(int i = 1 ; i <= n ; i ++) fa[i] = i;//重置并查集
    return ;
}

int main() {
    cin >> n >> m;
    reset();
    for(int i = 1 ; i <= m ; i ++) {
        int u , v , w;
        cin >> u >> v >> w;
        edge[++cnt].add(u,v,w);
        edge[++cnt].add(v,u,w);
        fa[find(u)] = find(v);//先合并，为了判断s，t的连通性
    }
    cin >> s >> t;
    if(!pd(s,t)) {
        cout << "IMPOSSIBLE";//如果在图中不连通，肯定无解
        return 0;
    }
    if(s == t){ cout << 0 ;return 0; }
    sort(edge + 1 , edge + 1 + cnt);//按照边权从小到大排序
    for(int i = 1 ; i < cnt ; i ++) { //枚举最小边
        int k,flag = 0;reset();
        for(int j = i ; j <= cnt ; j ++) {
            if(pd(s,t)) {flag = 1 ; break;}
            k = j;
            fa[find(edge[j].from)] = find(edge[j].to);
        }
        if(!flag) break;//假设已经不能用大于等于这个最小值的边权的边使得起点和终点联通，就没必要枚举了。
        int a = Ansa , b = Ansb , c = edge[k].w , d = edge[i].w;
        if(a * d - b * c > 0)//对应上面的柿子
        Ansa = edge[k].w , Ansb = edge[i].w;
    }
    if(Ansa % Ansb == 0) cout << Ansa / Ansb;//恰好能够整除按照题目要求是输出一个整数
    else cout << Ansa / __gcd(Ansa,Ansb) << "/" << Ansb / __gcd(Ansa,Ansb);//计算答案
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月22日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴