題目鏈接

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 (线段树、二叉堆、最小生成树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。