M_sea

洛谷2502 [HAOI2006]旅行
LuoguBZOJ分析最大边与最小边的比值最小$\Rightarrow$最大边尽量小,最小边尽量大。把所有的边排序...
扫描右侧二维码阅读全文
22
2019/01

洛谷2502 [HAOI2006]旅行

Luogu

BZOJ

分析

最大边与最小边的比值最小$\Rightarrow$最大边尽量小,最小边尽量大。

把所有的边排序后,枚举哪一条边是最小的。假设$i$是最小的。

然后从第$i$条边开始,从前往后加入边,直到$s$和$t$连通为止。

假设到第$j$条边的时候联通了,那么用$e[j].w/e[i].w$去更新答案。

判连通用并查集搞一下就行了。约分可以用__gcd,特判商为整数。

边界问题:一开始$ansmax$置为$30001$,$ansmin$置为$1$(卡住范围就行了)。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;
const int M=5000+10;

int n,m,s,t;
struct Edge { int u,v,w; };
Edge e[M];

inline int cmp(const Edge& a,const Edge& b) {
    return a.w<b.w;
}

int root[N];
inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i)
        e[i].u=read(),e[i].v=read(),e[i].w=read();
    s=read(),t=read();
    
    sort(e+1,e+m+1,cmp);
    int ansmax=30001,ansmin=1;
    for (re int i=1,j,flag;i<=m;++i) {
        init(n); flag=0;
        for (j=i;j<=m;++j) {
            int p=find(e[j].u),q=find(e[j].v);
            if (p!=q) root[p]=q;
            if (find(s)==find(t)) { flag=1; break; }
        }
        if (flag&&ansmax*e[i].w>ansmin*e[j].w)
            ansmin=e[i].w,ansmax=e[j].w;
    }
    
    if (ansmax==30001) puts("IMPOSSIBLE");
    else {
        int d=__gcd(ansmax,ansmin);
        if (d==ansmin) printf("%d\n",ansmax/ansmin);
        else printf("%d/%d\n",ansmax/d,ansmin/d);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 45 PM

发表评论