【bzoj1050】[HAOI2006]旅行comf

2015.05.25 17:17 Mon | 3次阅读 | 旧日oi | 固定链接 | 源码

Description

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

题解

看起来好像很难的样子,但是其实很水,把边按权值排序之后依次加入,每次加入之后进行bfs,如果s能到达t就可以用来更新答案,然后把当前可用的权值最小的边ban掉,然后继续bfs,直到s不能到达t。复杂度是多少呢。。O(mn)是肯定的了,每加入一条边平均要进行几次bfs就不知道了,但是应该是个不大的常数吧

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,s,t;
int ans1,ans2,now;
struct node{
    int u,v;
    int w;
}ed[5005];
bool cmp(const node a,const node &b)
{
    return a.w<b.w;
}
struct edge{
    int to;
    int next;
    int val;
}e[10005];
int h[505],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
bool vis[505];
queue<int> q;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
bool bfs()
{
    memset(vis,0,sizeof(vis));
    while(!q.empty()) q.pop();q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];e[i].to;i=e[i].next)
        if(!vis[v=e[i].to]&&e[i].val>=now)
        {
            vis[v]=1;
            if(v==t) return 1;
            q.push(v);
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
    cin>>s>>t;
    sort(ed+1,ed+m+1,cmp);
    for(int j=1,i=1;i<=m;i++) 
    {
        ae(ed[i].u,ed[i].v,ed[i].w);ae(ed[i].v,ed[i].u,ed[i].w);
        while(bfs()) 
        {
            if(ans1+ans2==0||ed[j].w*ans1>ans2*ed[i].w)
            ans1=ed[i].w,ans2=ed[j].w;
            now=ed[++j].w;
        }
    }
    if(ans1+ans2==0) puts("IMPOSSIBLE");
    else
    {
        int g=gcd(ans1,ans2);
        if(g==ans2) cout<<ans1/g<<endl;
        else cout<<ans1/g<<"/"<<ans2/g<<endl;
    }
}```