题意
给定 \(B,C\) 两个矩阵，你需要构造一张两权图 \(G=(V,E=\{(u,v,w_1,w_2)\})\) 使得从 \(i\) 到 \(j\) 之间：
- 可以只经过 \(w_1\ge B_{i,j}\) 的边连通
- 可以只经过 \(w_2\ge C_{i,j}\) 的边连通
- 不能只经过 \(w_1>B_{i,j}\) 的边连通
- 不能只经过 \(w_2>C_{i,j}\) 的边连通
构造方案或报告无解，边数限制 2023。
\(n\le 500\)。
分析
一眼看上去毫无思路，那我们就考虑弱化问题。如果只有 \(B\) 的限制该怎么做？
相当于构造一张图使得 \(i,j\) 之间路径的最小值的最大值为 \(B_{i,j}\)，这是最大生成树的形式（瓶颈树问题），故考虑构造出原图的最大生成树，那么如果一条边被加进最大生成树内，说明仅靠 \(>B_{i,j}\) 的边无法使两点连通，此时加入这条边是合法的，而且是必须加。若一条边没有被加进最大生成树，且 \(i,j\) 路径上的边的最小值 \(>B_{i,j}\)，则说明你这条边加不加都能使得 大于等于经过该最小值的边权 的边使两点连通，那么说明无解。
现在有两个边权了，其实也差不多，对 \(B,C\) 分别求出对应的最大生成树，由于可以有重边，所以我们大可不必去考虑边权和为 \(W\) 的限制，只需要让一条边的一个权值有用，另一个权值没用就行了。
但直接求最大生成树的并集是错的，因为有可能会出现类似于 \(W-B_{i,j}>C_{i,j}\) 的情况，这样的话 \(i,j\) 的边权最小值的最大值就是 \(W-B_{i,j}\) 了，这时这条边是不合法的，我们在求最小生成树的时候把这条边扔出去即可。
由于有无解情况，最后求出答案后用 floyd 检查一下合法性。
复杂度 \(O(n^3)\)，边数 \(2n-2\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("NO")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=505,maxm=2.5e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,W;
int c[maxn][maxn],b[maxn][maxn];
int a[2][maxn][maxn];
struct edge{
int u,v,w;
edge(int _u=0,int _v=0,int _w=0){u=_u,v=_v,w=_w;}
bool operator<(const edge &p)const{return w>p.w;}
}e[maxm];
int fa[maxn];
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
vector<edge>E;
inline void solve_the_problem(){
n=rd(),W=rd();
rep(i,1,n)rep(j,1,i-1)c[j][i]=rd();
rep(i,1,n)rep(j,1,i-1)b[j][i]=rd();
mem(a,~0x3f);
int cnt,tot;
cnt=0;rep(i,1,n)rep(j,i+1,n)if(b[i][j]+c[i][j]>=W)e[++cnt]=(edge){i,j,b[i][j]};
sort(e+1,e+cnt+1);
rep(i,1,n)fa[i]=i;
tot=0;
rep(i,1,cnt){
int gx=getf(e[i].u),gy=getf(e[i].v);
if(gx==gy)continue;
fa[gx]=gy,++tot;
a[0][e[i].u][e[i].v]=a[0][e[i].v][e[i].u]=max(a[0][e[i].u][e[i].v],e[i].w);
a[1][e[i].u][e[i].v]=a[1][e[i].v][e[i].u]=max(a[1][e[i].u][e[i].v],W-e[i].w);
E.emplace_back(edge(e[i].u,e[i].v,e[i].w));
}
if(tot!=n-1)return (void)PN;
cnt=0;rep(i,1,n)rep(j,i+1,n)if(b[i][j]+c[i][j]>=W)e[++cnt]=(edge){i,j,c[i][j]};
sort(e+1,e+cnt+1);
rep(i,1,n)fa[i]=i;
tot=0;
rep(i,1,cnt){
int gx=getf(e[i].u),gy=getf(e[i].v);
if(gx==gy)continue;
fa[gx]=gy,++tot;
a[1][e[i].u][e[i].v]=a[1][e[i].v][e[i].u]=max(a[1][e[i].u][e[i].v],e[i].w);
a[0][e[i].u][e[i].v]=a[0][e[i].v][e[i].u]=max(a[0][e[i].u][e[i].v],W-e[i].w);
E.emplace_back(edge(e[i].u,e[i].v,W-e[i].w));
}
if(tot!=n-1)return (void)PN;
rep(_,0,1)rep(k,1,n)rep(i,1,n)rep(j,1,n)a[_][i][j]=max(a[_][i][j],min(a[_][i][k],a[_][k][j]));
rep(i,1,n)rep(j,i+1,n)if(a[0][i][j]!=b[i][j]||a[1][i][j]!=c[i][j])return (void)PN;
write(E.size(),10);
for(auto i:E)write(i.u-1,32),write(i.v-1,32),write(i.w,10);
}
bool Med;
signed main(){
// freopen("bike.in","r",stdin);freopen("bike.out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/