【bzoj3218】a+b Problem 最小割+主席树

数据范围：$n≤5000$，$a,l,r≤10^9$，$b,w,p≤2\times 10^5$。

我们考虑一种暴力的最小割做法：

首先令$sum=\sum\limits_{i=1}^{n} b_i+w_i$

我们建一个图：

$S->i$，边权为$w_i$

$i->T$，边权为$b_i$

$i->i'$，边权为$p_i$

$j->i'$，边权为$∞$，（这里的i和j需要满足题目中的i,j限制）

然后我们对这个图跑一遍最小割，将$sum$减去这个值输出就是答案了。

这么建图总共需要$2n+2$个点，$O(n^2)$条边

 1 #include
 2 #define M 1000005
 3 #define N 150005
 4 #define INF 19890604
 5 using namespace std;
 6 
 7 struct edge{int u,v,next;}e[M]={0}; int head[N]={0},use=0;
 8 void add(int x,int y,int z){e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use++;}
 9 void ADD(int x,int y,int z){add(x,y,z); add(y,x,0);}
10 
11 int dis[N]={0},S,T; queue<int> q;
12 
13 bool bfs(){
14     memset(dis,0,sizeof(dis));
15     q.push(S); dis[S]=1;
16     while(!q.empty()){
17         int u=q.front(); q.pop();
18         for(int i=head[u];~i;i=e[i].next)
19         if(e[i].v&&dis[e[i].u]==0){
20             dis[e[i].u]=dis[u]+1;
21             q.push(e[i].u);
22         }
23     }
24     return dis[T];
25 }
26 
27 int dfs(int x,int flow){
28     if(x==T) return flow; int sum=0;
29     for(int i=head[x];~i;i=e[i].next)
30     if(e[i].v&&dis[x]+1==dis[e[i].u]){
31         int k=dfs(e[i].u,min(flow,e[i].v));
32         e[i].v-=k; e[i^1].v+=k;
33         sum+=k; flow-=k;
34         if(flow==0) return sum;
35     }
36     if(flow==0) dis[x]=-1;
37     return sum;
38 }
39 
40 int dinic(){
41     int res=0; 
42     while(bfs()) 
43     res+=dfs(S,1<<30); 
44 return res;}
45 
46 int n,sum=0;
47 int a[N]={0},b[N]={0},w[N]={0},l[N]={0},r[N]={0},p[N]={0},ok[N]={0};
48 
49 int main(){
50     scanf("%d",&n);
51     for(int i=1;i<=n;i++){
52         scanf("%d%d%d%d%d%d",a+i,b+i,w+i,l+i,r+i,p+i);
53         sum+=b[i]+w[i];
54     }
55     S=0,T=2*n+1;
56     memset(head,-1,sizeof(head));
57     for(int i=1;i<=n;i++) ADD(S,i,w[i]),ADD(i,T,b[i]),ADD(i+n,i,p[i]);
58     for(int i=1;i<=n;i++) for(int j=1;j)
59     if(l[i]<=a[j]&&a[j]<=r[i])
60     ADD(j,i+n,INF);
61     cout<endl;
62 }    

然后这个做法显然是会MLE的

我们发现原先的限制条件相当于在二维平面上框出一个允许的区间。

对于这种约束，我们可以用主席树来实现约束。

然后随便搞一搞就没了，注意细节。

 1 #include
 2 #define M 400000
 3 #define INF 19890604
 4 using namespace std;
 5 
 6 struct edge{int u,v,next;}e[M]={0}; int head[M]={0},use=0;
 7 void add(int x,int y,int z){e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use++;}
 8 void ADD(int x,int y,int z){add(x,y,z); add(y,x,0);}
 9 
10 int dis[M]={0},S,T; queue<int> q;
11 
12 bool bfs(){
13     memset(dis,0,sizeof(dis));
14     q.push(S); dis[S]=1;
15     while(!q.empty()){
16         int u=q.front(); q.pop();
17         for(int i=head[u];~i;i=e[i].next)
18         if(e[i].v&&dis[e[i].u]==0){
19             dis[e[i].u]=dis[u]+1;
20             q.push(e[i].u);
21         }
22     }
23     return dis[T];
24 }
25 
26 int dfs(int x,int flow){
27     if(x==T) return flow; int sum=0;
28     for(int i=head[x];~i;i=e[i].next)
29     if(e[i].v&&dis[x]+1==dis[e[i].u]){
30         int k=dfs(e[i].u,min(flow,e[i].v));
31         e[i].v-=k; e[i^1].v+=k;
32         sum+=k; flow-=k;
33         if(flow==0) return sum;
34     }
35     if(flow==0) dis[x]=-1;
36     return sum;
37 }
38 
39 int dinic(){int res=0; while(bfs()) res+=dfs(S,1<<30); return res;}
40 
41 int c[M]={0},a[M]={0},b[M]={0},w[M]={0},l[M]={0},r[M]={0},p[M]={0};
42 int lc[M]={0},rc[M]={0},cnt,rt=0,sum=0,n;
43 
44 void updata(int x,int l,int r,int ll,int rr,int id){
45     if(!x) return;
46     if(ll<=l&&r<=rr)return ADD(x,id,INF);
47     int mid=(l+r)>>1;
48     if(ll<=mid) updata(lc[x],l,mid,ll,rr,id);
49     if(mid1,r,ll,rr,id);
50 }
51 void updata(int &x,int l,int r,int id,int k){
52     cnt++; lc[cnt]=lc[x]; rc[cnt]=rc[x];
53     if(x) ADD(x,cnt,INF); x=cnt;
54     ADD(k,x,INF);
55     if(l==r) return;
56     int mid=(l+r)>>1;
57     if(id<=mid) updata(lc[x],l,mid,id,k);
58     else updata(rc[x],mid+1,r,id,k);
59 }
60 
61 int main(){
62     memset(head,-1,sizeof(head));
63     scanf("%d",&n);
64     for(int i=1;i<=n;i++){
65         scanf("%d%d%d%d%d%d",a+i,b+i,w+i,l+i,r+i,p+i);
66         c[i]=a[i]; sum+=b[i]+w[i];
67     }
68     sort(c+1,c+n+1);
69     for(int i=1;i<=n;i++){
70         a[i]=lower_bound(c+1,c+n+1,a[i])-c;
71         l[i]=lower_bound(c+1,c+n+1,l[i])-c;
72         r[i]=upper_bound(c+1,c+n+1,r[i])-c-1;
73     }
74     S=0; T=2*n+1; cnt=2*n+1;
75     for(int i=1;i<=n;i++){
76         ADD(S,i,w[i]);
77         ADD(i,T,b[i]);
78         ADD(i+n,i,p[i]);
79         if(l[i]<=r[i]) updata(rt,1,n,l[i],r[i],i+n);
80         updata(rt,1,n,a[i],i);
81     }
82     cout<endl;
83 }