淘宝 网站开发 退货,wordpress设置后台自定义功能选项,西安北郊网站开发,网站建设市场需求分析D. Best Edge Weight
给定一个有nnn个点mmm条边的无向连通图#xff0c;有mmm次询问#xff0c;每次询问第iii条边的权值最大为多少#xff0c;这张图的所有最小生成树的方案中#xff0c;一定包含第iii条边。
先跑一边最小生成树#xff0c;得到最小生成树#xff0c;…D. Best Edge Weight
给定一个有nnn个点mmm条边的无向连通图有mmm次询问每次询问第iii条边的权值最大为多少这张图的所有最小生成树的方案中一定包含第iii条边。
先跑一边最小生成树得到最小生成树然后依次统计答案分两种情况
1、这条边在最小生成树上
假设这条边的边权为valuevaluevalue把这条边断开则分成了两个集合A,BA, BA,B那么有一个性质从集合AAA连向集合BBB的边边权一定大于等于valuevaluevalue
如果从集合AAA连向集合BBB的边只有一条则这条边必定存在答案为−1-1−1。
如果从集合AAA连向集合BBB的边边权为valuevaluevalue的只有一条则答案为除这条边以外的最小边权 - 1。
否则的话答案就是value−1value - 1value−1了 。
2、这条边不在最小生成树上
考虑找到u−vu-vu−v路径上权值最大的边valuevaluevalue把这条边断开分成了两个集合A,BA, BA,B同样的有一个性质从集合AAA连向集合BBB的边边权一定大于等于valuevaluevalue
所以要使A,BA,BA,B集合联通且这条边一定出现则边权为value−1value - 1value−1即可。
对第 2 种情况可以考虑树链剖分然后线段树维护区间最大值即可单次询问复杂度lognlogn\log n \log nlognlogn考虑如何解决第一种情况。
对第 1 种情况用线段树维护一个区间最小值跟区间最小值个数然后单点查询最小值个数即可边权下放成点权树链剖分。
#include bits/stdc.h
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;const int N 2e5 10;int head[N], to[N 1], nex[N 1], value[N 1], cnt 1;int son[N], sz[N], dep[N], fa[N], rk[N], id[N], top[N], tot;int ff[N], vis[N], w[N], ans[N], n, m;struct Res {int u, v, w, id;bool operator (const Res t) const {return w t.w;}
}edge[N];void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}int find(int rt) {return ff[rt] rt ? rt : ff[rt] find(ff[rt]);
}void dfs1(int rt, int f) {fa[rt] f, dep[rt] dep[f] 1, sz[rt] 1;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}w[to[i]] value[i];dfs1(to[i], rt);sz[rt] sz[to[i]];if (!son[rt] || sz[to[i]] sz[son[rt]]) {son[rt] to[i];}}
}void dfs2(int rt, int tp) {rk[tot] rt, id[rt] tot, top[rt] tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}void Kruskal() {sort(edge 1, edge m 1);for (int i 1; i n; i) {ff[i] i;}for (int i 1, sum 0; i m sum n; i) {int u find(edge[i].u), v find(edge[i].v);if (u v) {continue;}ff[u] v, vis[i] 1, sum;add(edge[i].u, edge[i].v, edge[i].w);add(edge[i].v, edge[i].u, edge[i].w);}dfs1(1, 0);dfs2(1, 1);
}int maxn[N 2], minn[N 2], lazy[N 2];void push_up(int rt) {maxn[rt] max(maxn[ls], maxn[rs]);
}void push_down(int rt) {if (lazy[rt] ! 0x3f3f3f3f) {minn[ls] min(minn[ls], lazy[rt]), minn[rs] min(minn[rs], lazy[rt]);lazy[ls] min(lazy[ls], lazy[rt]), lazy[rs] min(lazy[rs], lazy[rt]);lazy[rt] 0x3f3f3f3f;}
}void build(int rt, int l, int r) {minn[rt] lazy[rt] 0x3f3f3f3f;if (l r) {maxn[rt] w[rk[l]];return ;}build(lson);build(rson);push_up(rt);
}void update(int rt, int l, int r, int L, int R, int v) {if (l L r R) {lazy[rt] min(lazy[rt], v);minn[rt] min(minn[rt], v);return ;}push_down(rt);if (L mid) {update(lson, L, R, v);}if (R mid) {update(rson, L, R, v);}
}int query_max(int rt, int l, int r, int L, int R) {if (l L r R) {return maxn[rt];}push_down(rt);int maxn 0;if (L mid) {maxn max(maxn, query_max(lson, L, R));}if (R mid) {maxn max(maxn, query_max(rson, L, R));}return maxn;
}int query_min(int rt, int l, int r, int x) {if (l r) {return minn[rt];}push_down(rt);if (x mid) {return query_min(lson, x);}else {return query_min(rson, x);}
}void update(int u, int v, int w) {while (top[u] ! top[v]) {if (dep[top[u]] dep[top[v]]) {swap(u, v);}update(1, 1, n, id[top[u]], id[u], w);u fa[top[u]];}if (u ! v) {if (dep[u] dep[v]) {swap(u, v);}update(1, 1, n, id[u] 1, id[v], w);}
}int query(int u, int v) {int maxn 0;while (top[u] ! top[v]) {if (dep[top[u]] dep[top[v]]) {swap(u, v);}maxn max(maxn, query_max(1, 1, n, id[top[u]], id[u]));u fa[top[u]];}if (u ! v) {if (dep[u] dep[v]) {swap(u, v);}maxn max(maxn, query_max(1, 1, n, id[u] 1, id[v]));}return maxn;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d %d, n, m);for (int i 1, u, v, w; i m; i) {scanf(%d %d %d, u, v, w);edge[i] {u, v, w, i};}Kruskal();build(1, 1, n);for (int i 1; i m; i) {if (!vis[i]) {update(edge[i].u, edge[i].v, edge[i].w);}}for (int i 1; i m; i) {if (vis[i]) {int u edge[i].u, v edge[i].v;if (dep[u] dep[v]) {swap(u, v);}int cur query_min(1, 1, n, id[u]);if (cur edge[i].w) {ans[edge[i].id] edge[i].w - 1;}else if (cur 0x3f3f3f3f) {ans[edge[i].id] -1;}else {ans[edge[i].id] cur - 1;}}else {ans[edge[i].id] query(edge[i].u, edge[i].v) - 1;}}for (int i 1; i m; i) {printf(%d%c, ans[i], i m ? \n : );}return 0;
}
