【学习笔记】[EGOI2023] Bikes vs Cars

学习笔记】[EGOI2023] Bikes vs Cars"/>

【学习笔记】[EGOI2023] Bikes vs Cars

题目链接

警惕出题人为了不让你看出来构造是生成树而用了 2023 2023 2023这个数字😅

下文中宽度为 w w w的边表示分配给自行车的宽度。

考虑如何判定无解。如果存在 i , j , k i,j,k i,j,k使得 b i , j < min ⁡ ( b i , k , b k , j ) b_{i,j}<\min(b_{i,k},b_{k,j}) bi,j​<min(bi,k​,bk,j​)或者 c i , j < min ⁡ ( c i , k , c k , j ) c_{i,j}<\min(c_{i,k},c_{k,j}) ci,j​<min(ci,k​,ck,j​)，那么原问题一定无解。

我们考虑，对于两个点 ( i , j ) (i,j) (i,j)，如果 b i , j + c i , j ≥ W b_{i,j}+c_{i,j}\ge W bi,j​+ci,j​≥W，那么我们可以贪心的在 i , j i,j i,j之间连一条宽度为 b i , j b_{i,j} bi,j​的边（给自行车道）以及一条宽度为 W − c i , j W-c_{i,j} W−ci,j​的边（给机动车道），这并不会影响答案；反之，如果 b i , j + c i , j < W b_{i,j}+c_{i,j}<W bi,j​+ci,j​<W，那么我们必然不能在 i , j i,j i,j之间连边。因此，考虑贪心的连上这些边，如果无法满足条件，那么原问题无解（我们已经尽可能的加入所有边了）。

考虑加上边数的限制，我们自然而然的想到分别求解这两类边对应的最大生成树，显然如果边数不为 2 n − 2 2n-2 2n−2那么原问题肯定无解；否则我们发现这样的生成树恰好满足我们的构造。（不需要 Floyd \text{Floyd} Floyd检验，可以结合第一步判定无解的过程想一想为什么）

复杂度 O ( n 3 ) O(n^3) O(n3)。但是显然判定无解的过程可以优化到 O ( n 3 w ) O(\frac{n^3}{w}) O(wn3​)。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
const int N=505;
int n,W,m,a[N][N],b[N][N];
int fa[N];
struct node{int x,y,z;bool operator <(const node &a)const{return z>a.z;}
}e[N*N];
vector<node>res;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>W;for(int i=1;i<n;i++){for(int j=0;j<i;j++){cin>>b[i][j];b[j][i]=b[i][j];}}for(int i=1;i<n;i++){for(int j=0;j<i;j++){cin>>a[i][j];a[j][i]=a[i][j];}}for(int i=0;i<n;i++)a[i][i]=b[i][i]=inf;for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]<min(a[i][k],a[k][j])||b[i][j]<min(b[i][k],b[k][j])){cout<<"NO";return 0;}}}}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(a[i][j]+b[i][j]>=W){e[++m]={i,j,a[i][j]};}}}sort(e+1,e+1+m);for(int i=0;i<n;i++)fa[i]=i;for(int i=1;i<=m;i++){int u=e[i].x,v=e[i].y,w=e[i].z;if(find(u)!=find(v))fa[fa[u]]=fa[v],res.pb({u,v,w});}for(int i=0;i<n;i++)fa[i]=i;m=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(a[i][j]+b[i][j]>=W){e[++m]={i,j,b[i][j]};}}}sort(e+1,e+1+m);for(int i=1;i<=m;i++){int u=e[i].x,v=e[i].y,w=e[i].z;if(find(u)!=find(v))fa[fa[u]]=fa[v],res.pb({u,v,W-w});}if(res.size()!=2*n-2){cout<<"No";return 0;}cout<<res.size()<<"\n";for(auto e:res){cout<<e.x<<" "<<e.y<<" "<<e.z<<"\n";}
}