「bzoj3218」a + b Problem - 主席树优化网络流建边 | Bill Yang's Blog

「bzoj3218」a + b Problem - 主席树优化网络流建边

题目大意


题目分析

先考虑暴力方法:
我们用割表示割去一条边,即不选该方案。
将所有权值累加,减去最小割即为答案。

考虑如何建图:
若$1\le j\le i,l_i\le a_j\le r_i$,那么若$i$是黑色,$j$是白色,就会产生额外代价$p_i$,这是一个二元组关系,我们这样建图表示约束关系:

可以使用$O(n^2)$暴力建边,但边数太多,网络流无法承受。

若不考虑位置的限制关系,仅仅剩下$l_i\le a_j\le r_i$的限制条件,这是一个权值区间,不难想到使用线段树拆分区间。线段树从上往下连边,每个$i$定位到线段树上$O(\log n)$个区间,故共$O(n+n\log n)$条边。
整个图长这个样子:

现在考虑$1\le j\le i$的限制,其是一个原序列的前缀,故不妨使用可持久化线段树对位置可持久化。
那么每次在$root[i-1]$加边,然后插入$root[i]$。
注意因为要包含以前的信息,故每个$root[i]$的区间要向$root[i-1]$对应区间连边。
整个图长这个样子:

跑网络流即可。


代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};
struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;
int n,cnt=0,tmp[maxn],a[maxn],l[maxn],r[maxn],root[maxn],ans=0;
struct President_Tree {
struct Tree {
int ls,rs,id;
} tree[maxn*10];
int size;
int insert(int pre,int left,int right,int id,int val) {
int now=++size;
tree[now]=tree[pre];
tree[now].id=++cnt;
if(tree[pre].id)dinic.AddEdge(tree[now].id,tree[pre].id,INT_MAX/2);
if(left==right) {
dinic.AddEdge(cnt,id,INT_MAX/2);
return now;
}
int mid=(left+right)>>1;
if(val<=mid) {
tree[now].ls=insert(tree[pre].ls,left,mid,id,val);
dinic.AddEdge(tree[now].id,tree[tree[now].ls].id,INT_MAX/2);
} else {
tree[now].rs=insert(tree[pre].rs,mid+1,right,id,val);
dinic.AddEdge(tree[now].id,tree[tree[now].rs].id,INT_MAX/2);
}
return now;
}
void query(int now,int left,int right,int Left,int Right,int p) {
if(left>Right||right<Left)return;
if(Left<=left&&Right>=right) {
dinic.AddEdge(p,tree[now].id,INT_MAX/2);
return;
}
int mid=(left+right)>>1;
query(tree[now].ls,left,mid,Left,Right,p);
query(tree[now].rs,mid+1,right,Left,Right,p);
}
} pt;
int main() {
n=Get_Int();
int S=2*n+1,T=2*n+2,tot=0;
cnt=T;
for(int i=1; i<=n; i++) {
tmp[++tot]=a[i]=Get_Int();
int b=Get_Int(),w=Get_Int();
ans+=b+w;
tmp[++tot]=l[i]=Get_Int();
tmp[++tot]=r[i]=Get_Int();
int p=Get_Int();
dinic.AddEdge(S,i,b);
dinic.AddEdge(i,T,w);
dinic.AddEdge(i,n+i,p);
}
sort(tmp+1,tmp+tot+1);
tot=unique(tmp+1,tmp+tot+1)-tmp-1;
for(int i=1; i<=n; i++) {
a[i]=lower_bound(tmp+1,tmp+tot+1,a[i])-tmp;
l[i]=lower_bound(tmp+1,tmp+tot+1,l[i])-tmp;
r[i]=lower_bound(tmp+1,tmp+tot+1,r[i])-tmp;
}
for(int i=1; i<=n; i++) {
if(i>1)pt.query(root[i-1],1,tot,l[i],r[i],n+i);
root[i]=pt.insert(root[i-1],1,tot,i,a[i]);
if(root[i-1])dinic.AddEdge(pt.tree[root[i]].id,pt.tree[root[i-1]].id,INT_MAX/2);
}
printf("%d\n",ans-dinic.maxflow(S,T));
return 0;
}
本篇文章有用吗?有用还不快点击!
0%