BZOJ 3218 UOJ #77 A+B Problem (主席樹、最小割)

大名鼎鼎的A+B Problem, 主席樹優(yōu)化最小割……

調(diào)題死活調(diào)不對，一怒之下改了一種寫法交上去A了，但是改寫法之后第4,5個點常數(shù)變大很多，于是喜提UOJ全站倒數(shù)第三

目前還不知道原來的寫法為什么是錯的，暫時先寫一下A掉的那種寫法的題解。

題目鏈接:

(BZOJ) https://www.lydsy.com/JudgeOnline/problem.php?id=3218

(UOJ) http://uoj.ac/problem/77

題解:

首先不難想到這樣的最小割建圖: (醒醒吧這種題就別老忘二分圖上想了) 下文用\(Edge(u,v,w)\)表示從\(u\)向\(v\)連一條邊權(quán)為\(w\)的單向邊, \(S,T\)分別是源點和匯點

對每一個方格建一個點\(V_i\)，然后\(Edge(S,V_i,b_i), Edge(V_i,T,w_i)\), 這樣一來這個點屬于\(T\)集(\(S\)的邊被割掉了)就表示這個點染成白色(舍棄\(b_i\)代價), 否則染成黑色。

此外對于每個方格再建新點\(E_i\), 然后\(Edge(V_i,E_i,p_i)\), 再對于滿足\(1\le j\le i, a_j\in[l_i,r_i]\)的\(j\), \(Edge(E_i,V_j,+\inf)\), 表示那個奇怪的方格的限制

至此網(wǎng)絡(luò)流建模結(jié)束。這個還是比較好想的，然而邊數(shù)\(O(n^2)\), \(TLE+MLE\)不謝。

然后我們考慮如果只有\(l_i\le a_i\le r_i\)這個限制，我們可以對\(a_i\)排序離散化之后轉(zhuǎn)化成了\(E_i\)這個點要向一個區(qū)間內(nèi)的\(V_j\)連邊，這樣的話我們可以建出一棵線段樹，線段樹每個節(jié)點向它的兩個兒子連邊，然后往區(qū)間連邊相當(dāng)于往這個區(qū)間拆成的\(O(\log n)\)個線段樹節(jié)點連邊，邊數(shù)\(O(\log n)\).

然而這題……還要\(1\le j\le i\)?

這樣我們就要把線段樹改成主席樹(vfk大毒瘤！)

后面的都是套路: 以\(i\)為歷史版本\(a_i\)為下標(biāo)建主席樹，然后主席樹的每個節(jié)點往兒子連邊，其余的連邊方式自行思考(很無腦)，詳見代碼。

有一個地方需要注意: 有種可能是我往主席樹里插入一個節(jié)點的時候，主席樹這個節(jié)點上已經(jīng)有值了。(也就是存在兩個\(a_i\)相等的情況)

這怎么辦呢？目前我還沒有找到一個我認(rèn)為合理的解決方法，最后直接簡單粗暴地離散化的時候不去重，強行把相等變成不等的辦法，導(dǎo)致UOJ上第4,5個點常數(shù)爆炸跑得和第9,10個點一樣慢，全站倒數(shù)第三，不過還是過了。

然后是目前這題的一些還未解決的問題，我想到了若干種彌補相等問題的做法，結(jié)果全都是50分或者80分，目前相對來說最靠譜的一種(答案和正確答案相差最小)是對于每一個重疊的主席樹節(jié)點\(T_i\)新建一個點\(T_i'\), \(Edge(T_{fa_i},T_i',+\inf), Edge(T_i',T_i,+\inf), Edge(T_i',T_j',+\inf)\) (\(fa_i\)表示主席樹的父親節(jié)點, \(j,j'\)是上一個歷史版本的對應(yīng)節(jié)點)。然而還是\(80\)分QAQ……所以哪位大佬能跟我說一下這個到底怎么解決啊，謝謝QwQ

代碼實現(xiàn)

離散化時不去重的版本，全站倒數(shù)第三

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #include<cassert> #define llong long long using namespace std;const int N = 8e4; const int M = 1e6; const llong INF = 100000000000ll; namespace NetFlow {struct Edge{int v,nxt,rev; llong w;} e[(M<<1)+3];int dep[N+3];int te[N+3];int fe[N+3];int que[N+3];int n,en,s,t;void addedge(int u,int v,llong w){ // printf("addedge %d %d %lld\n",u,v,w);en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[1] = s; dep[s] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[t]!=0;}llong dfs(int u,llong cur){if(u==t) return cur;llong rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && rst>0 && e[i].w>0){llong flow = dfs(e[i].v,min(e[i].w,rst));if(flow>0){e[i].w-=flow; rst-=flow; e[e[i].rev].w+=flow;if(e[i].w>0) {te[u] = i;}if(rst==0) return cur;}}}if(cur==rst) dep[u] = 0;return cur-rst;}llong dinic(){ // printf("Dinic n=%d\n",n);llong ret = 0ll;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(s,INF);}return ret;} } using NetFlow::addedge; using NetFlow::dinic;struct Element {llong b,w,p; int a,l,r; int id;bool operator <(const Element &arg) const{return a<arg.a;} } a[N+3],b[N+3]; struct SgTNode {int ls,rs; } sgt[N+3]; vector<int> disc; int rtn[N+3]; int n,siz;int getdisc(int x) {return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1; }void addval(int &pos,int le,int ri,int lrb,int id,llong w1,llong w2,llong w3) {siz++; sgt[siz] = sgt[pos];pos = siz;if(le==ri) {addedge(1,pos,w1); addedge(pos,id,w3); addedge(pos,2,w2); return;}int mid = (le+ri)>>1;if(lrb<=mid) {addval(sgt[pos].ls,le,mid,lrb,id,w1,w2,w3);}else {addval(sgt[pos].rs,mid+1,ri,lrb,id,w1,w2,w3);}if(sgt[pos].ls) {addedge(pos,sgt[pos].ls,INF);} //Judge 0if(sgt[pos].rs) {addedge(pos,sgt[pos].rs,INF);} }void AddEdge(int pos,int le,int ri,int lb,int rb,int id) {if(pos==0) return;if(lb<=le && rb>=ri) {addedge(id,pos,INF); return;}int mid = (le+ri)>>1;if(lb<=mid) {AddEdge(sgt[pos].ls,le,mid,lb,rb,id);}if(rb>mid) {AddEdge(sgt[pos].rs,mid+1,ri,lb,rb,id);} }int main() {scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%lld%lld%d%d%lld",&a[i].a,&a[i].b,&a[i].w,&a[i].l,&a[i].r,&a[i].p); a[i].id = i;disc.push_back(a[i].a);}sort(disc.begin(),disc.end());sort(a+1,a+n+1);for(int i=1; i<=n; i++){a[i].l = getdisc(a[i].l);a[i].r = getdisc(a[i].r+1)-1;if(a[i].l<1) a[i].l = 1;if(a[i].r>disc.size()) a[i].r = disc.size();a[i].a = i;b[a[i].id] = a[i];}for(int i=1; i<=n; i++) a[i] = b[i]; // for(int i=1; i<=n; i++) printf("%d %lld %lld %d %d %lld\n",a[i].a,a[i].b,a[i].w,a[i].l,a[i].r,a[i].p);siz = n+2;rtn[0] = 0;for(int i=1; i<=n; i++){ // printf("i%d:\n",i);rtn[i] = rtn[i-1];addval(rtn[i],1,disc.size(),a[i].a,i+2,a[i].b,a[i].w,a[i].p);AddEdge(rtn[i-1],1,disc.size(),a[i].l,a[i].r,i+2); // printf("siz=%d\n",siz); // for(int j=1; j<=i; j++) printf("rtn[%d]=%d\n",j,rtn[j]); // for(int j=n+3; j<=siz; j++) printf("i%d ls%d rs%d\n",j,sgt[j].ls,sgt[j].rs); // puts("");}NetFlow::n = siz; NetFlow::s = 1; NetFlow::t = 2;llong ans = 0ll;for(int i=1; i<=n; i++) ans += a[i].b+a[i].w;ans = ans-dinic();printf("%lld\n",ans);return 0; } /* 3 3 1 6 2 2 3 3 2 9 1 5 8 4 3 8 2 4 7 */

附: 80分代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #include<cassert> #define llong long long using namespace std;const int N = 8e4; const int M = 1e6; const llong INF = 100000000000ll; namespace NetFlow {struct Edge{int v,nxt,rev; llong w;} e[(M<<1)+3];int dep[N+3];int te[N+3];int fe[N+3];int que[N+3];int n,en,s,t;void addedge(int u,int v,llong w){ // printf("addedge %d %d %lld\n",u,v,w);en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[1] = s; dep[s] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[t]!=0;}llong dfs(int u,llong cur){if(u==t) return cur;llong rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && rst>0 && e[i].w>0){llong flow = dfs(e[i].v,min(e[i].w,rst));if(flow>0){e[i].w-=flow; rst-=flow; e[e[i].rev].w+=flow;if(e[i].w>0) {te[u] = i;}if(rst==0) return cur;}}}if(cur==rst) dep[u] = 0;return cur-rst;}llong dinic(){ // printf("Dinic n=%d\n",n);llong ret = 0ll;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(s,INF);}return ret;} } using NetFlow::addedge; using NetFlow::dinic;struct Element {llong b,w,p; int a,l,r; } a[N+3]; struct SgTNode {int ls,rs,prv; } sgt[N+3]; vector<int> disc; int rtn[N+3]; int n,siz;int getdisc(int x) {return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1; }void addval(int &pos,int le,int ri,int lrb,int id,llong w1,llong w2,llong w3,int prv) {siz++; sgt[siz] = sgt[pos];if(le==ri && pos!=0) {siz++; addedge(prv,siz,INF); addedge(siz,siz-1,INF); addedge(siz,sgt[pos].prv,INF); pos = siz-1; sgt[pos].prv = siz;}else pos = siz,sgt[pos].prv = siz;if(le==ri) {addedge(1,pos,w1); addedge(pos,id,w3); addedge(pos,2,w2); return;}int mid = (le+ri)>>1;if(lrb<=mid) {addval(sgt[pos].ls,le,mid,lrb,id,w1,w2,w3,pos);}else {addval(sgt[pos].rs,mid+1,ri,lrb,id,w1,w2,w3,pos);}if(sgt[pos].ls) {addedge(pos,sgt[pos].ls,INF);} //Judge 0if(sgt[pos].rs) {addedge(pos,sgt[pos].rs,INF);} }void AddEdge(int pos,int le,int ri,int lb,int rb,int id) {if(pos==0) return;if(lb<=le && rb>=ri) {addedge(id,pos,INF); return;}int mid = (le+ri)>>1;if(lb<=mid) {AddEdge(sgt[pos].ls,le,mid,lb,rb,id);}if(rb>mid) {AddEdge(sgt[pos].rs,mid+1,ri,lb,rb,id);} }int main() {scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%lld%lld%d%d%lld",&a[i].a,&a[i].b,&a[i].w,&a[i].l,&a[i].r,&a[i].p);disc.push_back(a[i].a);}sort(disc.begin(),disc.end());disc.erase(unique(disc.begin(),disc.end()),disc.end());for(int i=1; i<=n; i++){a[i].a = getdisc(a[i].a);a[i].l = getdisc(a[i].l);a[i].r = getdisc(a[i].r+1)-1;if(a[i].l<1) a[i].l = 1;if(a[i].r>disc.size()) a[i].r = disc.size();} // for(int i=1; i<=n; i++) printf("%d %lld %lld %d %d %lld\n",a[i].a,a[i].b,a[i].w,a[i].l,a[i].r,a[i].p);siz = n+2;rtn[0] = 0;for(int i=1; i<=n; i++){ // printf("i%d:\n",i);rtn[i] = rtn[i-1];addval(rtn[i],1,disc.size(),a[i].a,i+2,a[i].b,a[i].w,a[i].p,0);AddEdge(rtn[i-1],1,disc.size(),a[i].l,a[i].r,i+2); // printf("siz=%d\n",siz); // for(int j=1; j<=i; j++) printf("rtn[%d]=%d\n",j,rtn[j]); // for(int j=1; j<=siz; j++) printf("i%d ls%d rs%d\n",j,sgt[j].ls,sgt[j].rs); // puts("");}NetFlow::n = siz; NetFlow::s = 1; NetFlow::t = 2;llong ans = 0ll;for(int i=1; i<=n; i++) ans += a[i].b+a[i].w;ans = ans-dinic();printf("%lld\n",ans);return 0; } 發(fā)表于 2019-01-26 22:57 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3218 UOJ #77 A+B Problem (主席树、最小割)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。