洛谷P2888 [USACO07NOV]Cow Hurdles S 题解

题意：Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有 $N (1 ≤ N ≤ 300)$ 个站台，分别标记为 $1\dots N$ 。所有站台之间有 $M (1 ≤ M ≤ 25,000)$ 条单向路径，第i条路经是从站台 $S_i$ 开始，到站台 $E_i$ ，其中最高的栏的高度为$H_i (1 ≤ H_i ≤ 1,000,000)$。无论如何跑，奶牛们都要跨栏。奶牛们有 $T (1 ≤ T ≤ 40,000)$ 个训练任务要完成。第 $i$ 个任务包含两个数字 $A_i$ 和 $B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N)$，表示奶牛必须从站台 $A_i$ 跑到站台 $B_i$ ，可以路过别的站台。奶牛们想找一条路径从站台 $A_i$ 到站台 $B_i$ ，使路径上最高的栏的高度最小。你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

分析题目可以发现这是一张具有非负权重的有向图

我们只需要找到一条路径使得这条路径上所有的边权中最大值最小即可

Floyd解法

别看这个 $n\le300$ ，跑起来还是飞快地（数据有点水）

容易推出方程 f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));

不过我有点不放心就加了个小剪枝 qwq 虽然只快了3ms

代码如下

//Floyd
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
int n,m,Q,f[305][305];
signed main()
{
    read(n);read(m);read(Q);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=INF;
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        f[u][v]=min(f[u][v],w);
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            if(f[i][k]!=INF)
                for(int j=1; j<=n; j++)
                    f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
    while(Q--)
    {
        int x,y;read(x);read(y);
        write((f[x][y]==INF)?-1:f[x][y]);pc('\n');
    }
    return 0;
}

其他解法

关于SPFA，她死了。

~~开个玩笑而已~~

不过我们可以用理论复杂度较低的dijkstra

注意到 $N\le300$

那么离线解决即可

时间复杂度 $O(N^2\log M + T)$

不过实际情况下由于dijkstra常数较大，跑的甚至比Floyd慢…

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
struct Edge
{
    int u,v,w,next;
}e[50005];
struct node
{
    int u,mn;
    bool operator<(const node &o)const
    {
        return mn>o.mn;
    }
};
int pos=1,head[305];
int n,m,Q,d[305][305],vis[305];
void addEdge(int u,int v,int w)
{
    e[pos]={u,v,w,head[u]};
    head[u]=pos++;
}
void dijkstra(int st)
{
    priority_queue<node> q;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
        d[st][i]=INF;
    q.push({st,INF});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,t=max(d[st][u],e[i].w);
            if(t==INF)t=e[i].w;
            if(d[st][v]>t)
            {
                d[st][v]=t;
                if(!vis[v])
                    q.push({v,d[st][v]});
            }
        }
    }
}
signed main()
{
    read(n);read(m);read(Q);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        addEdge(u,v,w);
    }
    for(int i=1; i<=n; i++)
        dijkstra(i);
    while(Q--)
    {
        int x,y;read(x);read(y);
        write((d[x][y]==INF)?-1:d[x][y]);pc('\n');
    }
    return 0;
}