【BZOJ1050】旅行comf

1050: [HAOI2006]旅行comf

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 3132  Solved: 1718
[Submit][Status][Discuss]

Description

　　给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出
这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。

Input

　　第一行包含两个正整数，N和M。下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向
公路，车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速
度比最小的路径。s和t不可能相同。
1

Output

　　如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一
个既约分数。

Sample Input

【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3

Sample Output

【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2

HINT

 

Source

让我稍微口胡一下这道题 大概明白是什么意思

首先 我们可以知道一个废话的结论 但是这个结论非常重要！

你一定要记住 这个结论就是对于任意一个只有一部分边的最小生成树 最小边在答案中的生成树分母上

OK这样就很简单了

我们接下来只要满足一点：能构成最小生成树 即可

我们排序

枚举最小边 即我们认为这个边是最小的

然后我们做一遍 由于最大/最小 最小 即最大值最小 直接做 然后每次统计答案

感觉挺裸的但我智商不够用了= =

/*To The End Of The Galaxy*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#define debug(x) cerr<<#x<<"="<#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
struct edge
{
    int from,to,val,pre;
}Edge[5005];
int fa[505],head[505],rk[505];
bool cmp(edge a,edge b)
{
    return a.val<b.val;
}
int n,m,a,b,c,cnt=0;
inline void addedge(int from,int to,int val)
{
    ++cnt;
    Edge[cnt]=((edge){from,to,val,head[from]});
    head[from]=cnt;
}
int find(int x)
{
    if(x==fa[x])return x;
    else return fa[x]=find(fa[x]);
}
bool Union(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy)return false;
    else
    {
        if(rk[fx]>=rk[fy])
        {
            rk[fx]+=rk[fy];
            fa[fy]=fx;
        }
        else
        {
            rk[fy]+=rk[fx];
            fa[fx]=fy;
        }
    }
    return true;
}
int gcd(ll a,ll b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int S,T;
#ifdef unix
    #define LLD "%lld"
#else
    #define LLD "%I64d"
#endif
int main()
{
    n=init();m=init();
    for(int i=1;i<=m;i++)
    {
        a=init();b=init();c=init();
        addedge(a,b,c);
    }
    S=init();T=init();
    ll up,down,g,ansup=INF,ansdown=1;
    bool f=false;
    sort(Edge+1,Edge+1+cnt,cmp);
    for(int i=1;i<=m;i++)
    {
        f=false;
        up=0;
        for(int j=1;j<=n;j++)
        {
            rk[j]=1;fa[j]=j;
        }
        Union(Edge[i].from,Edge[i].to);
        down=Edge[i].val;
        up=Edge[i].val;
        if(find(S)==find(T))
        {
            f=true;
        }
        else
        {
            for(int j=i+1;j<=m;j++)
            {
                if(Union(Edge[j].from,Edge[j].to))
                {
                    up=max(up,(ll)Edge[j].val);
                    if(find(S)==find(T))
                    {
                        f=true;
                        break;
                    }
                }
            }
        }
        if(f)
        {
            g=gcd(up,down);
            up/=g;down/=g;
            if(up*ansdownansup)
            {
                ansup=up;ansdown=down;
            }
        }
    }
    if(ansup==INF)
    {
        printf("IMPOSSIBLE\n");
    }
    else
    {
        if(ansup%ansdown==0)printf(LLD"\n",ansup/ansdown);
        else printf(LLD"/"LLD,ansup,ansdown);
    }
    return 0;
}
数据结构-并查集图论-最小生成树

相关

标签