P9466 [EGOI2023] Bikes vs Cars / 骑车与汽车题解

Zi_Gao · 2023-11-13 22:46:12 · 题解

前言

今天模拟赛 C 题题解啊，但是这个题确实惊艳到我了。

正文

0x00 题目分析

简化题面：

给定一个 n\leq 500 个点的完全图，每条边有两个权值 B,C 满足 B+C=W，请你求出一个与其等价的图，使得其边数少于 2023。并且与原图等价，其中等价的定义为：

每两个点 u,v 之前都可通过一条路径，这条路径上边权 B 的最小值等于 B_{u,v}。且不存在一条路径使得路径上边权 B 的最小值大于 B_{u,v}。

同理定义 C 权值。

图联通

可能无解。期望时间复杂度 \mathcal{O}\left(n^3\right)。

考虑只能用很少边，不如直接考虑能不呢用一个树给他们穿起来，而且时间复杂度很充裕。

0x01 解决问题

发现两个边权非常难搞啊，考虑简化版本的问题变成只有边权 B。此时发现一个图无解的充分必要条件显然是：存在一组互不相同的点 u,v,k 使得 B_{u,v}\lt\min\left(B_{u,k},B_{k,v}\right)，那么有界的充分不要条件是对于任意互不相同的点 u,v,k 都有 B_{u,v}\geq\min\left(B_{u,k},B_{k,v}\right)。

然后考虑找出一个可行方案，可以对这个原来的完全图跑一个最大生成树，会发现一个有意思的东西。若存在一对点 u,v，边 \left(u,v,B_{u,v}\right) 其中 w 是权值，是非树边，记 Bmin_{u,v} 表示树上 u 到 v 路径上的边权最小值：

首先根据上面的结论有 B_{u,v}\geq Bmin_{u,v}。
由于这是最大生成树，那么这条边有 B_{u,v}\leq Bmin_{u,v} 若不是则这条边会被加入最大生成树。

推出 B_{u,v}= Bmin_{u,v}，意思是我们根本就不用管非树边~~是不是很神奇！！！~~

现在考虑加上另一个边权 C，不妨考虑直接分开建立最大生成树，然后缝在一起。但是会发现个问题，会加入一些不能加入的边，可以发现这些满足不能加入的边满足一个性质就是 B_{u,v}+C_{u,v}\lt W 显然不可能加入，总有一个会无法满足。考虑直接删除这些边，然后两个权值分开做，跑最大生成树，跑完进行一个类似 Floyd 的算法吧两两点的最大可以走到的权值跑出来，形式化的：B_{u,v}=\max\left\{\min\left(B_{u,k},B_{k,v}\right),B_{u,v}\right\}。然后去与原图比较即可，判断是否无解。思考一下这样为啥是对的？首先对于 B_{u,v}+C_{u,v}\geq W 这样的边两个最大生成树中肯定不会互相干扰；其次对于 B_{u,v}+C_{u,v}\lt W 这样的边也没有问题，因为若有问题的话就算换个生成树的方式仍然有问题，都不会存在问题。

0x02 代码实现

非常好写啊。

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

const int UFDS_SIZE=510;
struct UFDS{
    int parents[UFDS_SIZE];

    void build(int n){
        for(register int i=1;i<=n;++i)
            parents[i]=i;
        return;
    }

    int find(int x){
        return x==parents[x]?x:(parents[x]=find(parents[x]));
    }

    int find_b(int x){
        while(parents[x]!=x)
            x=parents[x];
        return x;
    }

    void merge(int i,int j){
        parents[find(i)]=find(j);
        return;
    }

    void clear(){
        for(int i=1;i<UFDS_SIZE;i++)
            parents[i]=i;
        return;
    }
}UB,UC;

#define NOOOOOO \
{puts("NO");\
return 0;}

struct EDGE{
    int u,v,w;
    bool operator < (const EDGE o) const{
        return w>o.w;
    }
};

std::vector<EDGE> edges_b,edges_c,outE;

int B[510][510],C[510][510],Bnew[510][510],Cnew[510][510];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    memset(Bnew,~0x3f,sizeof(Bnew));
    memset(Cnew,~0x3f,sizeof(Cnew));

    register int i,j,k,u,v,W;

    int n=read();
    W=read();

    for(u=0;u<n;++u)
        for(v=0;v<u;++v)
            B[u][v]=B[v][u]=read();
    for(u=0;u<n;++u)
        for(v=0;v<u;++v)
            C[u][v]=C[v][u]=read();

    for(u=0;u<n;++u)
        for(v=0;v<u;++v)
            for(k=0;k<n;++k)
                if(k!=u&&k!=v&&(B[u][v]<std::min(B[u][k],B[k][v])||C[u][v]<std::min(C[u][k],C[k][v]))) NOOOOOO

    for(u=0;u<n;++u)
        for(v=0;v<u;++v)
            if(B[u][v]+C[u][v]>=W){
                edges_b.push_back((EDGE){u,v,B[u][v]});
                edges_c.push_back((EDGE){u,v,C[u][v]});
            }

    std::sort(edges_b.begin(),edges_b.end());
    std::sort(edges_c.begin(),edges_c.end());

    UB.build(n),UC.build(n);

    for(auto edge:edges_b)
        if(UB.find(edge.u)!=UB.find(edge.v))
            Bnew[edge.u][edge.v]=Bnew[edge.v][edge.u]=edge.w,
            outE.push_back((EDGE){edge.u,edge.v,W-edge.w}),
            UB.merge(edge.u,edge.v);

    for(auto edge:edges_c)
        if(UC.find(edge.u)!=UC.find(edge.v))
            Cnew[edge.u][edge.v]=Cnew[edge.v][edge.u]=edge.w,
            outE.push_back(edge),
            UC.merge(edge.u,edge.v);

    for(k=0;k<n;++k)
        for(u=0;u<n;++u)
            for(v=0;v<u;++v)
                if(k!=u&&k!=v)
                    Bnew[u][v]=Bnew[v][u]=std::max(Bnew[u][v],std::min(Bnew[u][k],Bnew[k][v])),
                    Cnew[u][v]=Cnew[v][u]=std::max(Cnew[u][v],std::min(Cnew[u][k],Cnew[k][v]));

    for(u=0;u<n;++u)
        for(v=0;v<u;++v)
            if(B[u][v]!=Bnew[u][v]||C[u][v]!=Cnew[u][v]||Bnew[u][v]<0||Cnew[u][v]<0) NOOOOOO

    print(outE.size()),putchar('\n');
    for(auto edge:outE) print(edge.u),putchar(' '),print(edge.v),putchar(' '),print(edge.w),putchar('\n');

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

总结

非常有意思的题，重点在于大力观察出两个重要的不等式，啊啊啊太厉害了。

P9466 [EGOI2023] Bikes vs Cars / 骑车与汽车 题解

前言

正文

0x00 题目分析

0x01 解决问题

0x02 代码实现

总结

P9466 [EGOI2023] Bikes vs Cars / 骑车与汽车题解