[HAOI2006]旅行COMF

枚举上界和下界用判断连通,复杂度

枚举下界,上界可以二分,理论复杂度似乎能冲...但是T了

枚举下界,然后使用并查集动态加入边判断连通,复杂度,可以通过

枚举下界,使用取每个点最优(小)的上界。但是不知道可不可以,没试过

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct edge
{
    int l,r,w;
}d[maxn];
int mu,zi,n,m,s,t,pre[maxn];
double ans = 1e9;
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
void UP(int down,int up)
{
    if( (double)up/down>ans )    return;
    ans = (double)up/down;
    mu = up, zi = down;    
}
bool com(edge a,edge b){ return a.w<b.w; }
int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]); }
void join(int q,int w){ pre[find(q)]=find(w); return; }
int main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].w);

    cin >> s >> t;
    sort( d+1,d+1+m,com );
    for(int i=1;i<=m;i++)
    {
        for(int q=1;q<=n;q++)    pre[q] = q;
        for(int j=i;j<=m;j++)
        {
            join( d[j].l,d[j].r );
            if( find(s)==find(t) )    { UP(d[i].w,d[j].w); break; }
        }
    }
    if( zi==mu&&zi==0 )    printf("IMPOSSIBLE");
    else if( mu%zi==0 )    cout << mu/zi;
    else    cout << mu/gcd(zi,mu) << "/" << zi/gcd(zi,mu);
}