算法思路

核心思想

使用最大生成树 + 合法性验证的方法：

1. 验证三角不等式：检查给定的 C 和 B 矩阵是否满足最宽路径的性质
2. 分别构建两个网络：分别对汽车和自行车构建最大生成树
3. 合并边集：将两个生成树的边合并作为最终网络

关键观察

• 对于最宽路径问题，矩阵必须满足：a[i][j] >= min(a[i][k], a[k][j])
• 这是三角不等式的变种，确保了路径宽度的合理性
• 如果 a[i][j] + b[i][j] < W，则该对节点无法同时满足要求

代码详解

数据结构定义

int n, W;              // 节点数和街道总宽度
int a[N][N], b[N][N];  // 汽车和自行车的要求矩阵
int fa[N];             // 并查集父节点
vector<pair<int, pair<int,int> > > eds, seq;  // 边集和排序序列

三角不等式验证

for(int i=0;i<n;i++) for(int j=0;j<i;j++) for(int k=0;k<n;k++) 
    if(i!=k&&j!=k){
        // 检查汽车要求的三角不等式
        if(a[i][j] < min(a[i][k], a[k][j])){
            puts("NO");
            return 0;
        }
        // 检查自行车要求的三角不等式
        if(b[i][j] < min(b[i][k], b[k][j])){
            puts("NO");
            return 0;
        }
    }

解释：如果存在 a[i][j] < min(a[i][k], a[k][j])，那么通过 i->k->j 的路径会有更宽的汽车道，与 a[i][j] 是最大值的定义矛盾。

构建汽车网络

// 初始化并查集
for(int i=0;i<n;i++) fa[i]=i;

// 将所有边按汽车要求值从大到小排序
for(int i=0;i<n;i++) for(int j=0;j<i;j++) 
    seq.push_back(make_pair(a[i][j], make_pair(i,j)));
sort(seq.begin(),seq.end());
reverse(seq.begin(),seq.end());

// 处理相同权值的边
for(int i=0,j;i<seq.size();i=j){
    // 处理所有权值相同的边
    for(j=i;j<seq.size()&&seq[j].F==seq[i].F;j++){
        int x=seq[j].S.F, y=seq[j].S.S;
        // 如果可以同时满足汽车和自行车要求，且不在同一连通块
        if(a[x][y]+b[x][y]>=W && getf(x)!=getf(y)){
            fa[getf(x)]=getf(y);  // 合并连通块
            eds.push_back(make_pair(W-a[x][y], make_pair(x,y)));
        }
    }
    // 检查所有该权值的边是否都在同一连通块
    for(int k=i;k<j;k++){
        int x=seq[k].S.F, y=seq[k].S.S;
        if(getf(x)!=getf(y)){
            puts("NO");
            return 0;
        }
    }
}

关键点：

• 按汽车要求值从大到小处理，这是最大生成树的思想
• a[x][y]+b[x][y]>=W 确保可以分配宽度满足双方要求
• 自行车道宽度设为 W-a[x][y]，即剩余宽度给汽车

构建自行车网络（类似逻辑）

seq.clear();
for(int i=0;i<n;i++) fa[i]=i;

// 按自行车要求值排序
for(int i=0;i<n;i++) for(int j=0;j<i;j++) 
    seq.push_back(make_pair(b[i][j], make_pair(i,j)));
sort(seq.begin(),seq.end());
reverse(seq.begin(),seq.end());

// 类似处理...
for(int i=0,j;i<seq.size();i=j){
    for(j=i;j<seq.size()&&seq[j].F==seq[i].F;j++){
        int x=seq[j].S.F, y=seq[j].S.S;
        if(a[x][y]+b[x][y]>=W && getf(x)!=getf(y)){
            fa[getf(x)]=getf(y);
            eds.push_back(make_pair(b[x][y], make_pair(x,y)));
        }
    }
    for(int k=i;k<j;k++){
        int x=seq[k].S.F, y=seq[k].S.S;
        if(getf(x)!=getf(y)){
            puts("NO");
            return 0;
        }
    }
}

差异：这里自行车道宽度设为 b[x][y]

输出结果

printf("%d\n", eds.size());
for(auto &[w,e]: eds) 
    printf("%d %d %d\n", e.F, e.S, w);

算法原理

为什么这样构造是可行的？

1. 三角不等式保证：确保存在满足要求的路径
2. 最大生成树保证：为每个权值等级构建最宽路径
3. 并查集验证：确保所有要求相同的节点都已连通
4. 互补条件：a[x][y] + b[x][y] >= W 确保可以分配宽度

边数分析

• 每次添加边都连接两个不同的连通块
• 最多添加 2*(n-1) 条边（两个生成树）
• 满足 2023 条边的限制（n ≤ 500）

样例分析

样例1验证

输入：

2 1
1
1

• a[0][1]=1, b[0][1]=1
• a+b=2 ≥ 1，满足条件
• 构建两条边：(0,1,0) 和 (0,1,1)
• 正确：一条纯汽车道，一条纯自行车道

样例2验证

输入：

4 1
0
0 1
0 0 1
1
1 1
1 1 1

• 检查三角不等式会发现矛盾
• 例如 a[1][3]=0 但 min(a[1][2], a[2][3]) = 1
• 输出 NO

算法优势

1. 正确性保证：通过严格的数学验证
2. 效率高：$O(n^3)$ 验证 + $O(n^2 \log n)$ 建树
3. 边数少：最多 $2n-2$ 条边
4. 实现简洁：使用并查集和排序

关键技巧

1. 三角不等式验证：快速排除不可行情况
2. 按权值分组处理：确保相同权值的节点连通
3. 互补条件判断：a+b ≥ W 是可行的必要条件
4. 双生成树构造：分别满足汽车和自行车要求