BZOJ 4388 [JOI2012春季合宿]Invitation (线段树、二叉堆、最小生成树)

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4388

题解

模拟Prim算法？
原题所述的过程就是Prim算法求最大生成树的过程。于是我们可以知道起始点并没有影响。
那么就用数据结构模拟Prim算法吧。
首先离散化所有区间，每个区间只需要一个点和外面相连，其余点均按照覆盖该点区间的最大权值与这个点相连。因此简单利用线段树即可求出这一部分的答案。
对于剩下的部分，用维护\(T\)表示目前没有加入的点，先加入左边\(1\)号点，同时用大根堆维护已加入点和未加入点之间的连边（也就是有一部分已加入一部分未加入的区间）
每次从堆中取出一个区间，随便找一个该区间内还在\(T\)集中的点（若不存在就什么都不干），把它从\(T\)集中删掉，顺便把包含它的所有没访问过的区间加入队列
这个可以使用线段树实现，两棵线段树分别维护两边的点，把每个区间拆成\(\log\)段，放到线段树的每个节点上，顺便维护每个区间内依然存在的点的最大值（或最小值，目的就是随便找一个点），每次删掉一个点的时候删掉线段树从根到它的所有区间并扔进堆里，并且把这个点标记为不存在（最大值改成\(0\)）.
这一部分使用vector实现可能会MLE，可以使用链表实现。
总时间复杂度\(O(n\log n)\).

代码

#include<bits/stdc++.h> #define llong long long #define pii pair<int,int> #define mkpr make_pair using namespace std;const int N = 2e5; const int SIZ = 3.5e6;struct Element {int lx,ly,rx,ry; llong w;bool operator <(const Element &arg) const {return w>arg.w;} } qr[N+3]; priority_queue<pii> pq; bool del[N+3];struct SegmentTree {struct List{int nxt,val;} li[SIZ+3];struct SgTNode{int fe;int maxi;} sgt[(N<<2)+3];int siz;void build(int u,int le,int ri){sgt[u].maxi = ri;if(le==ri) {return;}int mid = (le+ri)>>1;build(u<<1,le,mid); build(u<<1|1,mid+1,ri);}void insert(int u,int le,int ri,int lb,int rb,int x){if(lb>rb) {return;}if(le>=lb && ri<=rb) {siz++; li[siz].nxt = sgt[u].fe; li[siz].val = x; sgt[u].fe = siz; return;}int mid = (le+ri)>>1;if(lb<=mid) {insert(u<<1,le,mid,lb,rb,x);}if(rb>mid) {insert(u<<1|1,mid+1,ri,lb,rb,x);}}int query(int u,int le,int ri,int lb,int rb){if(lb>rb) {return 0;}if(le>=lb && ri<=rb) {return sgt[u].maxi;}int mid = (le+ri)>>1,ret = 0;if(lb<=mid) {ret = max(ret,query(u<<1,le,mid,lb,rb));}if(rb>mid) {ret = max(ret,query(u<<1|1,mid+1,ri,lb,rb));}return ret;}void delet(int u,int le,int ri,int pos){for(int &i=sgt[u].fe; i; i=li[i].nxt){if(!del[li[i].val]) {del[li[i].val] = true; pq.push(mkpr(qr[li[i].val].w,li[i].val));}}if(le==ri) {sgt[u].maxi = 0; return;}int mid = (le+ri)>>1;if(pos<=mid) {delet(u<<1,le,mid,pos);}else {delet(u<<1|1,mid+1,ri,pos);}sgt[u].maxi = max(sgt[u<<1].maxi,sgt[u<<1|1].maxi);} } sgt1,sgt2;struct SegmentTree2 {int maxi[(N<<2)+3];void insert(int u,int le,int ri,int lb,int rb,int x){if(lb>rb) return;if(le>=lb && ri<=rb) {maxi[u] = max(maxi[u],x); return;}int mid = (le+ri)>>1;if(lb<=mid) {insert(u<<1,le,mid,lb,rb,x);}if(rb>mid) {insert(u<<1|1,mid+1,ri,lb,rb,x);}}int query(int u,int le,int ri,int pos){if(le==ri) {return maxi[u];}int mid = (le+ri)>>1;if(pos<=mid) {return max(maxi[u],query(u<<1,le,mid,pos));}else {return max(maxi[u],query(u<<1|1,mid+1,ri,pos));}} } sgt3,sgt4;vector<int> discx,discy; int n,m,q; llong ans;int getdiscx(int x) {return lower_bound(discx.begin(),discx.end(),x)-discx.begin();} int getdiscy(int x) {return lower_bound(discy.begin(),discy.end(),x)-discy.begin();}int main() {scanf("%d%d%*d%d",&n,&m,&q);for(int i=1; i<=q; i++){scanf("%d%d%d%d%lld",&qr[i].lx,&qr[i].rx,&qr[i].ly,&qr[i].ry,&qr[i].w);discx.push_back(qr[i].lx-1),discx.push_back(qr[i].rx),discy.push_back(qr[i].ly-1),discy.push_back(qr[i].ry);}discx.push_back(0),discy.push_back(0);sort(discx.begin(),discx.end()); discx.erase(unique(discx.begin(),discx.end()),discx.end());sort(discy.begin(),discy.end()); discy.erase(unique(discy.begin(),discy.end()),discy.end());for(int i=1; i<=q; i++){qr[i].lx = getdiscx(qr[i].lx-1)+1,qr[i].rx = getdiscx(qr[i].rx),qr[i].ly = getdiscy(qr[i].ly-1)+1,qr[i].ry = getdiscy(qr[i].ry);}n = discx.size()-1,m = discy.size()-1;sgt1.build(1,1,n); sgt2.build(1,1,m);for(int i=1; i<=q; i++){sgt3.insert(1,1,n,qr[i].lx,qr[i].rx,qr[i].w);sgt4.insert(1,1,m,qr[i].ly,qr[i].ry,qr[i].w);sgt1.insert(1,1,n,qr[i].lx,qr[i].rx,i);sgt2.insert(1,1,m,qr[i].ly,qr[i].ry,i);}for(int i=1; i<=n; i++){ans += 1ll*sgt3.query(1,1,n,i)*(discx[i]-discx[i-1]-1ll);}for(int i=1; i<=m; i++){ans += 1ll*sgt4.query(1,1,m,i)*(discy[i]-discy[i-1]-1ll);}sgt1.delet(1,1,n,1);while(!pq.empty()){int i = pq.top().second; pq.pop();int ux = sgt1.query(1,1,n,qr[i].lx,qr[i].rx);if(ux){ans += qr[i].w;sgt1.delet(1,1,n,ux);pq.push(mkpr(qr[i].w,i));continue;}int uy = sgt2.query(1,1,m,qr[i].ly,qr[i].ry);if(uy){ans += qr[i].w;sgt2.delet(1,1,m,uy);pq.push(mkpr(qr[i].w,i));}}if(sgt1.sgt[1].maxi||sgt2.sgt[1].maxi) {puts("-1"); return 0;}printf("%lld\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的BZOJ 4388 [JOI2012春季合宿]Invitation (线段树、二叉堆、最小生成树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。