题解：P9466 [EGOI 2023] Bikes vs Cars / 骑车与汽车

Danielcdo · 2026-06-08 17:28:53 · 题解

一般在模拟赛中看到图论或构造的题我都会跳掉。

Solution

稍作转化。修改一下分割道路，我们定义 a_{i,j}=W-c_{i,j}。限制转化为 (i,j) 间路径最大边的最小值为 a_{i,j}，与 b_{i,j} 的限制对称。

接着，我们先讨论只有 a_{i,j} 限制的情况如何构造。一个关键观察是，对于任意三个点 i、j 和 k，a_{i,j}\le \max(a_{i,k},a_{k,j})；否则无解。假设有解，则上述不等式一定成立。那么根据这个性质，我们若按照 a_{i,j} 建立无向完全图，则考虑任意点对 (i,j) 间路径最大边的最小值：

• 下界为 a_{i,j}，因为根据刚才的性质，不存在路径最大值更小。
• 上界为 a_{i,j}，因为 i 和 j 之间存在边权为 a_{i,j} 的连边。

于是我们得出结论，这样的完全图一定符合要求。但是完全图边数是 O(n^2) 的，考虑简化。由于“路径最大边的最小值”只涉及最小生成树上的边，于是我们只用保留最小生成树上的边即可，边数优化为 O(n)。

然后添加 b_{i,j} 的限制。先进行类似的处理，建出完全图然后跑出最大生成树。此时一个错误的想法是直接对这两棵生成树的边集取并，但是这样合并可能会影响生成树的形态。具体地：

• 若 b_{i,j}<a_{i,j}，那么 (i,j) 间路径最大边的最小值会取到 b_{i,j}， (i,j) 间路径最小边的最大值会取到 a_{i,j}，这下两边都不能满足。但我们也不能直接判定为无解，因为他们可能通过其他路径满足，所以在建完全图时，直接不考虑这两条边。
• 否则 b_{i,j}\ge a_{i,j}。那么合并对两棵生成树不会产生影响。考虑 Kruskal 算法流程。我们在求最小生成树对边排序时，b_{i,j} 一定会排在 a_{i,j} 之后，那么一定不会被选，也就不会影响最小生成树了；最大生成树同理，也不会被影响。

于是就做完了。记得构造完进行判定是否为有效解，无效则输出无解。判定方法为先判定连通性，然后逐个求每个点对是否同时满足 a_{i,j} 和 b_{i,j}，这个过程可以建出生成树然后跑 dfs，也可以直接 Floyd 暴力算。时间复杂度 O(n^2\log n) 或 O(n^3)，取决于你懒不懒。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read()
{
    char c=getchar();
    int f=1,x=0;
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int N=5e2+5,inf=1e9;
int n,k,m,cnt,a[N][N],b[N][N],f[N][N],g[N][N];
struct edge{int u,v,w;}e1[N*N],e2[N*N],e[N*N];
inline bool cmp1(edge x,edge y){return x.w<y.w;}
inline bool cmp2(edge x,edge y){return x.w>y.w;}
struct dsu
{
    int fa[N];
    inline void init(){for(int i=1;i<=n;i++) fa[i]=i;}
    inline int findfa(int x)
    {
        if(x==fa[x]) return x;
        return fa[x]=findfa(fa[x]);
    }
}d;
void kru1()
{
    d.init();
    sort(e1+1,e1+1+m,cmp1);
    for(int i=1;i<=m;i++)
    {
        int u=e1[i].u,v=e1[i].v;u=d.findfa(u),v=d.findfa(v);
        if(u==v) continue;d.fa[v]=u,e[++cnt]=e1[i];
    }
}
void kru2()
{
    d.init();
    sort(e2+1,e2+1+m,cmp2);
    for(int i=1;i<=m;i++)
    {
        int u=e2[i].u,v=e2[i].v;u=d.findfa(u),v=d.findfa(v);
        if(u==v) continue;d.fa[v]=u,e[++cnt]=e2[i];
    }
}
void check()
{
    int tot=0;
    d.init();
    for(int i=1;i<=cnt;i++)
    {
        int u=e[i].u,v=e[i].v;
        u=d.findfa(u),v=d.findfa(v);
        if(u==v) continue;
        d.fa[v]=u;tot++;
    }
    if(tot!=n-1){puts("NO");exit(0);}
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) f[i][j]=(i==j?-inf:inf),g[i][j]=-f[i][j];
    for(int i=1;i<=cnt;i++)
    {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        f[u][v]=f[v][u]=min(f[u][v],w),g[u][v]=g[v][u]=max(g[u][v],w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],max(f[i][k],f[k][j])),g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[i][j]!=f[i][j]||b[i][j]!=g[i][j]){puts("NO");exit(0);}
}
int main()
{
    n=read(),k=read();
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++) a[i][j]=k-read();
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            b[i][j]=read();if(b[i][j]<a[i][j]) continue;
            e1[++m]={i,j,a[i][j]},e2[m]={i,j,b[i][j]};
        }
    kru1(),kru2();
    check();
    print(cnt);
    for(int i=1;i<=cnt;i++) putchar('\n'),print(e[i].u-1),putchar(' '),print(e[i].v-1),putchar(' '),print(e[i].w);
    return 0;
}