BZOJ3218: A + B Problem

最小割·主席樹

題解：

用主席樹優化最小割orz

orz orz orz orz orz

orz orz orz orz orz

orz POPOQQQ orz

orz orz orz orz orz

orz orz orz orz orz

調試1.5h+

Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl 
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;

inline void read(int &num){
    num=; char c; int bo=;
    while(!isdigit(c=getchar()) && c!='-');
    if(c=='-') bo=-;
    else num=c-'0';
    while(isdigit(c=getchar())) num=num*+c-'0';
    num*=bo;
}

int S, T, n, tp[N], tpsz; ll ans;
int a[],b[],w[],l[],r[],p[];
int lch[N], rch[N], root[N], sz;

struct Edge{
    int to,next,cap,flow;
} e[];
int head[N], ec=;
void add(int a,int b,int cap){
    ec++; e[ec].cap=cap; e[ec].flow=;
    e[ec].to=b; e[ec].next=head[a]; head[a]=ec;
}
void add2(int a,int b,int cap){
    add(a,b,cap); add(b,a,);
}

int d[N]; bool vis[N];
bool bfs(){
    memset(vis,false,sizeof(vis));
    memset(d,-,sizeof(d));
    queue<int> q; q.push(S); vis[S]=true; d[S]=;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(!vis[v] && e[i].cap>e[i].flow){
                vis[v]=true; d[v]=d[u]+; q.push(v);
                if(v==T) return true;
            }
        }
    }
    return false;
}

int dfs(int u,int a){
    if(u==T || a==) return a;
    int flow=, f;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(d[v]==d[u]+ && (f=dfs(v,min(a,e[i].cap-e[i].flow)))){
            e[i].flow+=f; e[i^].flow-=f; flow+=f; a-=f;
            if(a==) break;
        }
    }
    if(a) d[u]=-;
    return flow;
}

ll dinic(){
    ll flow=;
    while(bfs()){ flow+=dfs(S,INF); }
    return flow;
}

void insert(int &x,int t,int p,int id,int l=,int r=tpsz){
    x=++sz; lch[x]=lch[t]; rch[x]=rch[t];
    add2(id,x+n*,INF); if(t)add2(t+n*,x+n*,INF);     
    if(l!=r){
        int mid=(l+r)>>;
        if(p<=mid){ insert(lch[x],lch[t],p,id,l,mid); }
        else{ insert(rch[x],rch[t],p,id,mid+,r); }
    }
}

void find(int &x,int t,int ql,int qr,int id,int l=,int r=tpsz){
    if(!x) return;
    if(ql<=l && r<=qr){ add2(x+n*,id+n,INF); return; }
    int mid=(l+r)>>;
    if(ql<=mid){ find(lch[x],lch[t],ql,qr,id,l,mid); }
    if(qr>mid){ find(rch[x],rch[t],ql,qr,id,mid+,r); }
}

void build(){
    S=N-; T=S+;
    for(int i=;i<=n;i++){
        add2(S,i,w[i]); add2(i,T,b[i]);
        add2(i+n,i,p[i]);
    }

    for(int i=;i<=n;i++){
        if(i>) find(root[i-],root[i-],l[i],r[i],i);
        insert(root[i],root[i-],a[i],i);
    }
}

int main(){
    freopen("3218.in","r",stdin);
    read(n); tpsz=;
    for(int i=;i<=n;i++){
        read(a[i]); read(b[i]); read(w[i]); 
        read(l[i]); read(r[i]); read(p[i]);
        ans+=w[i]; ans+=b[i];
        tp[++tpsz]=a[i]; tp[++tpsz]=l[i]; tp[++tpsz]=r[i];
    }
    sort(tp,tp+tpsz); tpsz=unique(tp,tp+tpsz)-tp;
//  D(tpsz); E;
    for(int i=;i<=n;i++){
        a[i]=lower_bound(tp,tp+tpsz,a[i])-tp+;
        l[i]=lower_bound(tp,tp+tpsz,l[i])-tp+;
        r[i]=lower_bound(tp,tp+tpsz,r[i])-tp+;
//      D(a[i]); D(l[i]); D(r[i]); E;
    }
    build();
    ans-=dinic();
    printf("%lld\n",ans);
}
           

最後來寫一下我為啥一直WA。。。

出來手殘少些了一些addedge外

罪魁禍首就是想着在一個root裡面插入多條鍊，還想着這幾條鍊公共部分共用點的zz主席樹（你明白這是啥吧。。。不知道也沒關系，可能隻有我這種zz能想出這種zz寫法。。。）

我一開始在查找區間的時候走到沒有建立的點也建立點，其實根本就不用，直接傳回就行了。因為下面沒有點，反正也不會有流量。

總之不要像我這樣zz！