[HAOI2006]旅行

题意

思路

可以算作“神奇的解法”一类了。。。

做法很简单，看你想不想的到而已，对边权排序，从小到大枚举边，以这条边为最短边做最小生成树就行了

Code

#include<bits/stdc++.h>
#define N 505
#define M 5005
using namespace std;
int n,m,s,t,fa[N];
int maxx,minn;
double Minn=444444444;
struct Edge
{
    int u,v,w;
}edge[M];

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
bool cmp(Edge a,Edge b) {return a.w<b.w;} 
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int gcd(int a,int b) {return (!b) ? a : gcd(b,a%b);}
int main()
{
    read(n);read(m);
    for(int i=1;i<=m;++i) read(edge[i].u),read(edge[i].v),read(edge[i].w);
    sort(edge+1,edge+m+1,cmp);
    read(s);read(t);
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j) fa[j]=j;
        for(int j=i;j<=m;++j)
        {
            int fu=find(edge[j].u),fv=find(edge[j].v);
            if(fu!=fv) fa[fu]=fv;
            if(find(s)==find(t))
            {
                if(Minn>(double)edge[j].w/edge[i].w)
                {
                    Minn=(double)edge[j].w/edge[i].w;
                    maxx=edge[j].w;
                    minn=edge[i].w;
                }
            }
        }
    }
    if(maxx==0) printf("IMPOSSIBLE\n");
    else if(maxx%minn) printf("%d/%d\n",maxx/gcd(maxx,minn),minn/gcd(maxx,minn));
    else printf("%d\n",maxx/minn);
    return 0;
}

[HAOI2006]旅行

原文：https://www.cnblogs.com/Chtholly/p/11628489.html