题目很难懂啊，我真的想吐槽了...

题目 P9466

（对我来说）易懂版：（感觉没理解错）

现在有 $n$ 个点，每对点给出了两个变量 $C_{i,j}$ 和 $B_{i,j}$。 你需要构造一张“合法”的联通图。 图的每条边 $s$ 宽度为 $W$，你需要将宽度划分为两部分，分别记为 $s_b$ 和 $s_c$。

合法： 对于每一对点 $i，j$ 之间的所有路径，对于每一条路径用 $T_x$ 记录路径间 $s_b$ 的最小值，满足 $\max \{T_x\} = B_{i,j}$，用 $K_x$ 记录路径间 $s_c$ 的最小值，满足 $\max \{K_x\} = C_{i,j}$。

分析

首先考虑合法的必要条件之一：对于三个不同的点 $i, j, k$ 必须满足 $B_{i,j} \ge \min \{ B_{i,k}, B_{k,j}\}$。$C$ 同理。（可以反证法证明）

如果建一张完全图，在数据合法的情况下一定合法，但完全图的边有很多，考虑能不能建树。

我们先只考虑 $B$，以 $B$ 为依据建最大生成树。对于任意三个不同的点 $i, j, k$，如果遍历到 $B_{i,j}$ 时 $i,j$ 已联通，那么满足 $B_{i,j} \le \min\{B_{i,k}, B{k,j}\}$。再结合之前的必要条件，我们就得到了 $B_{i,j} = \min\{B_{i,k}, B{k,j}\}$，则此时哪怕不把 $B_{i,j}$ 加入也是合法的。

单独考虑 $C$ 建树同理。

然后我们把两张图结合起来。 对于现在的图，我们加入的边有一个对应的 $C'_{i,j} = W - B_{i,j}$。如果 $C'_{i,j} > C_{i,j}$，那么我们将无法满足 $i,j$ 间最短路的最大值为 $C_{i,j}$ 所以这种边（即 $B_{i,j} + C_{i,j} < W$ 的边）是一定不能加进去的，在建树的时候之间跳过就行。（$B'$ 是一样的）。 再考虑 $B_{i,j} + C_{i,j} \ge W$ 的情况是否合法。此时 $C'_{i,j} \le C_{i,j}$ 则在把两张图结合起来后，不影响最小值最大为 $C_{i,j}$，是合法的。$B'$ 同理。

综上，在把不合法的边都舍弃的情况下，分别以 $B,C$ 为依据建最大生成树，然后再把它们结合起来就是答案。 如果不连通则无解。

代码

我的代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 600;

int n, w;
int c[maxn][maxn], b[maxn][maxn], f[maxn];
bool visb[maxn][maxn], visc[maxn][maxn];

int find(int x){
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}

void uni(int x, int y){
	x = find(x), y = find(y);
	f[x] = y;
}

struct E{
	int u, v, w;
	bool operator < (const E &x)const{
		return w > x.w;
	}
};

vector<E> eb, ec;

bool check(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				if(i == j || j == k || i == k) continue;
				if(b[i][j] < min(b[i][k], b[k][j])) return 0;
				if(c[i][j] < min(c[i][k], c[k][j])) return 0;
			}
		}
	}
	return 1;
}

int main(){
	
	cin >> n >> w;
	for(int i = 1; i < n; i++){
		for(int j = 0; j < i; j++){
			cin >> c[j][i];
			c[i][j] = c[j][i];
		}
	}
	
	for(int i = 1; i < n; i++){
		for(int j = 0; j < i; j++){
			cin >> b[j][i];
			b[i][j] = b[j][i];
		}
	}
	
	if(!check()) return cout << "NO" << endl, 0;
	
	for(int j = 1; j < n; j++){
		for(int i = 0; i < j; i++){
			if(b[i][j] + c[i][j] >= w){
				eb.push_back({i, j, b[i][j]});
				ec.push_back({i, j, c[i][j]});
			}
		}
	}
	
	sort(eb.begin(), eb.end());
	sort(ec.begin(), ec.end());
	
	for(int i = 0; i < n; i++) f[i] = i;
	for(auto e : eb){
		int u = e.u, v = e.v;
		if(find(u) == find(v)) continue;
		uni(u, v);
		visb[u][v] = 1;
	}
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(f[i] == i) cnt++;
		f[i] = i;
	}
	
	if(cnt != 1) return cout << "NO" << endl, 0;
	
	for(auto e : ec){
		int u = e.u, v = e.v;
		if(find(u) == find(v)) continue;
		uni(u, v);
		visc[u][v] = 1;
	}
	
	cnt = 0;
	for(int i = 0; i < n; i++){
		if(f[i] == i) cnt++;
	}
	
	if(cnt != 1) return cout << "NO" << endl, 0;
	
	vector<E> ans;
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(visb[i][j]){
				ans.push_back({i, j, b[i][j]});
			}
			if(visc[i][j]){
				ans.push_back({i, j, w - c[i][j]});
			}
		}
	}
	
	cout << ans.size() << endl;
	for(auto e : ans){
		cout << e.u << " " << e.v << " " << e.w << endl; 
	}

	return 0;
}