【bzoj3218/UOJ#77】a+b Problem

  • 用主席树优化网络流真是一颗赛艇

题解

首先看到这种题目,就有一种最小割的冲动,其实正解就是最小割

这题$POPOQQQ$大爷讲的非常好,传送门

注意维护主席树时,如果到了叶子节点,我们需要连一条从上一版本的树所对应的节点出发指向该叶子节点的边,这样做的原因很显然

PS:$bzoj$丧心病狂卡空间,蒟蒻只好膜拜了$Cydiater$的代码才卡过去

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 5010
#define INF 1000000000
using namespace std;
struct node{int y,next,v,rel;}e[MAXN<<7];
int n,len,cnt,tot,ans,S,T,Link[MAXN<<6],A[MAXN],B[MAXN],W[MAXN],P[MAXN],L[MAXN],R[MAXN],num[MAXN<<6],hash[MAXN<<6];
int level[MAXN<<6],root[MAXN],son[MAXN<<6][2],id[MAXN][2];
queue<int> q;
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
void add(int x,int y,int v){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].rel=len+1;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;e[len].rel=len-1;
}
int find(int x){
int l=1,r=tot;
while(l+1<r){
int mid=(l+r)>>1;
if(hash[mid]<=x)l=mid;
else r=mid;
}
return hash[l]==x?l:r;
}
int newnode(int last){
son[++cnt][0]=son[last][0];
son[cnt][1]=son[last][1];
return cnt;
}
void insert(int l,int r,int &root,int last,int x,int pos){
root=newnode(last);
if(l==r) {add(pos,root,INF);if(last) add(last,root,INF); return;}
int mid=(l+r)>>1;
if(x<=mid) insert(l,mid,son[root][0],son[last][0],x,pos);
else insert(mid+1,r,son[root][1],son[last][1],x,pos);
if(son[root][0]) add(son[root][0],root,INF);
if(son[root][1]) add(son[root][1],root,INF);
}
void query(int l,int r,int root,int x,int y,int pos){
if(x>r||y<l) return;
if(x<=l&&y>=r) {add(root,pos,INF); return;}
int mid=(l+r)>>1;
if(mid>=x) query(l,mid,son[root][0],x,y,pos);
if(mid+1<=y) query(mid+1,r,son[root][1],x,y,pos);
}
bool bfs(){
memset(level,-1,sizeof(level));
q.push(S); level[S]=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=Link[x];i;i=e[i].next)
if(level[e[i].y]<0&&e[i].v){
q.push(e[i].y);
level[e[i].y]=level[x]+1;
}
}
return level[T]>=0;
}
int MAXFLOW(int x,int flow){
if(x==T) return flow;
int maxflow=0,d=0;
for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
if(e[i].v&&level[e[i].y]==level[x]+1)
if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow))){
e[i].v-=d; e[e[i].rel].v+=d; maxflow+=d;
}
if(!maxflow) level[x]=-1;
return maxflow;
}
void solve(){
int d=0;
while(bfs()) while(d=MAXFLOW(S,INF)) ans-=d;
printf("%d\n",ans);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read();
for(int i=1;i<=n;++i){
A[i]=read(); B[i]=read();W[i]=read();L[i]=read();R[i]=read();P[i]=read();
num[++cnt]=A[i]; num[++cnt]=L[i]; num[++cnt]=R[i]; ans+=B[i]+W[i];
}
sort(num+1,num+cnt+1); hash[++tot]=num[1];
for(int i=2;i<=cnt;++i) if(num[i]!=num[i-1]) hash[++tot]=num[i];
cnt=0; S=++cnt; T=++cnt;
for(int i=1;i<=n;++i){
id[i][0]=++cnt; id[i][1]=++cnt;
add(S,id[i][0],W[i]); add(id[i][0],T,B[i]);
add(id[i][1],id[i][0],P[i]); query(1,tot,root[i-1],find(L[i]),find(R[i]),id[i][1]);
insert(1,tot,root[i],root[i-1],find(A[i]),id[i][0]);
}
solve();
return 0;
}
文章目录
  1. 1. 题解
  2. 2. 参考代码
,