网站建设调查问卷,新东方,app产品开发流程,选择宁波seo优化公司Description
给定一个 n n n 个点、 m m m 条边的图#xff0c;有 q q q 次询问#xff0c;每次询问一个 [ l , r ] [l,r] [l,r] 的区间#xff0c;求将 n n n 个点分为两个部分后#xff0c;编号在 [ l , r ] [l,r] [l,r] 内的边中#xff0c;两端点属于同一部分的…Description
给定一个 n n n 个点、 m m m 条边的图有 q q q 次询问每次询问一个 [ l , r ] [l,r] [l,r] 的区间求将 n n n 个点分为两个部分后编号在 [ l , r ] [l,r] [l,r] 内的边中两端点属于同一部分的边权最大值最小是多少。
Solution
转换一下题意删去一些边使得剩下的图是一个二分图使得删去的边权最大值最小。
上来看到最大值最小立马想到二分答案每次二分一个边权 m i d mid mid将所有边权大于 m i d mid mid 的加入图中用扩展域并查集判断是否是二分图。
时间复杂度 O ( q log m ( n m α ( n ) ) ) O(q\log m(nm\alpha(n))) O(qlogm(nmα(n)))。
但是你发现 O ( log m ) O(\log m) O(logm) 是没必要的先将边按边权从大到小排序若编号属于 [ l , r ] [l,r] [l,r] 就加入图中如果加完这条边变奇图了那么这条边的边权就是答案。
时间复杂度 O ( q ( n m α ( n ) ) ) O(q(nm\alpha(n))) O(q(nmα(n)))由于 CF的神仙机子以及 6 6 6 秒的实现可以暴力通过。
考虑如何优化发现每一次加入边后的图实际上只有 O ( n ) O(n) O(n) 条边会对下次加边造成影响即一些树边可能是森林和可能有的一条边权最大的非树边当前答案它们可以代表当前的图同时一些边在多组询问中都被并入一次而将询问上到线段树上就可以避免。
所以我们开一棵线段树节点 [ l , r ] [l,r] [l,r] 表示将编号 [ l , r ] [l,r] [l,r] 的边并完后能代表这个图的 O ( n ) O(n) O(n) 条边同时按边权从大到小排序合并时先归并排序将左右儿子的代表边集和在一起然后求出新图的代表边集建树复杂度为 O ( m log m α ( n ) ) O(m\log m\alpha(n)) O(mlogmα(n))。
查询时将 [ l , r ] [l,r] [l,r] 的代表边集暴力求答案复杂度 O ( q n α ( n ) log m ) O(qn\alpha(n)\log m) O(qnα(n)logm)。
还可以继续将询问离线离散化树上节点 [ l , r ] [l,r] [l,r] 表示 [ b l , b r 1 ) [b_l,b_{r1}) [bl,br1) 区间的代表边集其中 b b b 是离散数组。
记得离散询问 [ l , r ] [l,r] [l,r] 时离散 l l l 和 r 1 r1 r1查询时取出 [ c l , c r 1 − 1 ] [c_l,c_{r1}-1] [cl,cr1−1] 的代表集暴力即可其中 c i c_i ci 表示 i i i 离散后的编号若询问中没有 1 1 1 和 m m m记得加进离散。
时间复杂度 O ( m log q α ( n ) q n α ( n ) log q ) O(m\log q\alpha(n)qn\alpha(n)\log q) O(mlogqα(n)qnα(n)logq)。
Code
#includebits/stdc.h
using namespace std;
#define ls x1
#define rs x1|1
struct edge{int x,y,z;
}e[1000010];
bool cmp(edge x,edge y){return x.zy.z;
}
#define ve vectoredge
int n,m,q,tot;
int b[6060],siz[2020],fa[2020];
ve tr[4000040];
struct que{int l,r;
}qu[3030];
int find(int x){if(fa[x]x) return x;return fa[x]find(fa[x]);
}
bool uni(int x,int y){int fxfind(x),fyfind(y);if(fxfy) return 0;if(siz[fx]siz[fy]) swap(fx,fy);siz[fy]siz[fx];fa[fx]fy;return 1;
}
void reset(int x){fa[x]x,fa[xn]xn;siz[x]1,siz[xn]1;
}
pairve,int solve(ve tmp){ve ans;for(auto x:tmp){reset(x.x),reset(x.y);}for(auto i:tmp){int xfind(i.x),yfind(i.y);if(x!y){if(uni(i.x,i.yn)uni(i.y,i.xn)){ans.push_back(i);}}else{ans.push_back(i);return {ans,i.z};break;}}return {ans,-1};
}
ve merge(ve l,ve r){ve tmp;int fl10,fl20;while(fl1l.size()fl2r.size()){if(cmp(l[fl1],r[fl2])){tmp.push_back(l[fl1]);}else{tmp.push_back(r[fl2]);}}while(fl1l.size()) tmp.push_back(l[fl1]);while(fl2r.size()) tmp.push_back(r[fl2]);auto anssolve(tmp);return ans.first;
}
void build(int x,int l,int r){if(lr){ve tmp;for(int ib[l];ib[l1];i){tmp.push_back(e[i]);}sort(tmp.begin(),tmp.end(),cmp);auto anssolve(tmp);tr[x]ans.first;return ;}int midlr1;build(ls,l,mid),build(rs,mid1,r);tr[x]merge(tr[ls],tr[rs]);
}
ve query(int x,int l,int r,int L,int R){if(lLrR){return tr[x];}int midlr1;if(Rmid) return query(ls,l,mid,L,R);if(Lmid1) return query(rs,mid1,r,L,R);return merge(query(ls,l,mid,L,R),query(rs,mid1,r,L,R));
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cinnmq;for(int i1;im;i){cine[i].xe[i].ye[i].z;}for(int i1;iq;i){cinb[tot]b[tot];b[tot];qu[i]{b[tot-1],b[tot]};}b[tot]1;sort(b1,b1tot);totunique(b1,b1tot)-b-1;b[tot1]m1; //注意细节build(1,1,tot);for(int i1;iq;i){int llower_bound(b1,b1tot,qu[i].l)-b;int rlower_bound(b1,b1tot,qu[i].r)-b-1;ve tmpquery(1,1,tot,l,r);int anssolve(tmp).second;coutans\n;}return 0;
}
