如何做企业黄页网站,wordpress ip 地址修改,默认网站停止,网页设计网站建设的基本流程题目链接
警惕出题人为了不让你看出来构造是生成树而用了 2023 2023 2023这个数字#x1f605;
下文中宽度为 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,…题目链接
警惕出题人为了不让你看出来构造是生成树而用了 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,jmin(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,jmin(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,jci,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,jci,jW那么我们必然不能在 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)。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
const int N505;
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 za.z;}
}e[N*N];
vectornoderes;
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);cinnW;for(int i1;in;i){for(int j0;ji;j){cinb[i][j];b[j][i]b[i][j];}}for(int i1;in;i){for(int j0;ji;j){cina[i][j];a[j][i]a[i][j];}}for(int i0;in;i)a[i][i]b[i][i]inf;for(int k0;kn;k){for(int i0;in;i){for(int j0;jn;j){if(a[i][j]min(a[i][k],a[k][j])||b[i][j]min(b[i][k],b[k][j])){coutNO;return 0;}}}}for(int i0;in;i){for(int ji1;jn;j){if(a[i][j]b[i][j]W){e[m]{i,j,a[i][j]};}}}sort(e1,e1m);for(int i0;in;i)fa[i]i;for(int i1;im;i){int ue[i].x,ve[i].y,we[i].z;if(find(u)!find(v))fa[fa[u]]fa[v],res.pb({u,v,w});}for(int i0;in;i)fa[i]i;m0;for(int i0;in;i){for(int ji1;jn;j){if(a[i][j]b[i][j]W){e[m]{i,j,b[i][j]};}}}sort(e1,e1m);for(int i1;im;i){int ue[i].x,ve[i].y,we[i].z;if(find(u)!find(v))fa[fa[u]]fa[v],res.pb({u,v,W-w});}if(res.size()!2*n-2){coutNo;return 0;}coutres.size()\n;for(auto e:res){coute.x e.y e.z\n;}
}
