从前有个
n
n
n 个方格排成一行,从左至右依此编号为
1
,
2
,
⋯
,
n
1,2,⋯,n
1,2,⋯,n。
有一天思考熊想给这
n
n
n 个方格染上黑白两色。
第
i
i
i 个方格上有
6
6
6 个属性:
a
i
,
b
i
,
w
i
,
l
i
,
r
i
,
p
i
a_i,b_i,w_i,l_i,r_i,p_i
ai,bi,wi,li,ri,pi。
如果方格
i
i
i 染成黑色就会获得
b
i
b_i
bi 的好看度。
如果方格
i
i
i 染成白色就会获得
w
i
w_i
wi 的好看度。
但是太多了黑色就不好看了。如果方格
i
i
i 是黑色,并且存在一个
j
j
j 使得
1
≤
j
<
i
1≤j<i
1≤j<i 且
l
i
≤
a
j
≤
r
i
l_i≤a_j≤r_i
li≤aj≤ri 且方格
j
j
j 为白色,那么方格
i
i
i 就被称为奇怪的方格。
如果方格
i
i
i 是奇怪的方格,就会使总好看度减少
p
i
p_i
pi。
也就是说对于一个染色方案,好看度为:
∑
方格 i 为黑色
b
i
+
∑
方格 i 为白色
w
i
−
∑
方格 i 为奇怪的方格
p
i
∑_\text{方格 i 为黑色}b_i+∑_\text{方格 i 为白色}w_i−∑_\text{方格 i 为奇怪的方格}p_i
方格 i 为黑色∑bi+方格 i 为白色∑wi−方格 i 为奇怪的方格∑pi
现在给你
n
,
a
,
b
,
w
,
l
,
r
,
p
n,a,b,w,l,r,p
n,a,b,w,l,r,p,问所有染色方案中最大的好看度是多少。
设
a
m
a
x
a_{max}
amax 为
a
,
l
,
r
a,l,r
a,l,r 中的最大值,
v
m
a
x
v_{max}
vmax 为
b
,
w
b,w
b,w 中的最大值,
p
m
a
x
p_{max}
pmax 为
p
p
p 中的最大值。
测试点编号
n
n
n
a
m
a
x
a_{max}
amax
v
m
a
x
v_{max}
vmax
p
m
a
x
p_{max}
pmax
1
1
1
=
5
=5
=5
≤
10
≤10
≤10
≤
10
≤10
≤10
≤
10
≤10
≤10
2
2
2
=
20
=20
=20
≤
40
≤40
≤40
≤
40
≤40
≤40
≤
40
≤40
≤40
3
3
3
=
20
=20
=20
≤
40
≤40
≤40
≤
40
≤40
≤40
≤
40
≤40
≤40
4
4
4
=
5000
=5000
=5000
≤
10
≤10
≤10
≤
200000
≤200000
≤200000
≤
100000
≤100000
≤100000
5
5
5
=
5000
=5000
=5000
≤
10
≤10
≤10
≤
200000
≤200000
≤200000
≤
300000
≤300000
≤300000
6
6
6
=
200
=200
=200
≤
109
≤109
≤109
≤
200000
≤200000
≤200000
≤
200000
≤200000
≤200000
7
7
7
=
300
=300
=300
≤
109
≤109
≤109
≤
200000
≤200000
≤200000
≤
220000
≤220000
≤220000
8
8
8
=
500
=500
=500
≤
109
≤109
≤109
≤
200000
≤200000
≤200000
≤
400000
≤400000
≤400000
9
9
9
=
5000
=5000
=5000
≤
5000
≤5000
≤5000
≤
200000
≤200000
≤200000
≤
150000
≤150000
≤150000
10
10
10
=
5000
=5000
=5000
≤
109
≤109
≤109
≤
200000
≤200000
≤200000
≤
300000
≤300000
≤300000
2
s
,
48
M
B
\tt 2\,s,48\,MB
2s , 48MB
最大的好看度,可以转化为:总好看度(含 b,w) - 最小损失好看度(含 b,w,p)
于是,可以用网络流最小割解决“最小损失好看度”的问题。
令
S
,
T
S,T
S,T 为源点、汇点,
S
S
S 部表示涂黑色,
T
T
T 部表示涂白色。
我们把每个点
i
i
i 连两条边:
S
→
i
S\rightarrow i
S→i(边权为
b
i
b_i
bi,若保留,则表示
i
i
i 涂黑色),
i
→
T
i\rightarrow T
i→T(边权为
w
i
w_i
wi ,若保留,则表示
i
i
i 涂白色)。
对于每个
i
i
i ,新建一个点
i
′
i'
i′,与每个满足
1
≤
j
<
i
,
l
i
≤
a
j
≤
r
i
1\leq j<i,l_i\leq a_j\leq r_i
1≤j<i,li≤aj≤ri 的
j
j
j 连一条边
i
′
→
j
i'\rightarrow j
i′→j (边权为
+
∞
+\infty
+∞),然后连一条边
i
→
i
′
i\rightarrow i'
i→i′(边权为
p
i
p_i
pi),这样,如果所有的
j
j
j 有任意一个是白色(
j
→
T
j\rightarrow T
j→T 保留),为了使
S
,
T
S,T
S,T 不可达,就必须保留
i
→
T
i\rightarrow T
i→T 断掉
S
→
i
S\rightarrow i
S→i(选白色),或者保留
S
→
i
S\rightarrow i
S→i 断掉
i
→
i
′
i\rightarrow i'
i→i′ (选黑色,但是多付出
p
i
p_i
pi 的代价)。
虽然建图可以随便完成,但是边的数量太多,不仅空间存不下(48 Mb),而且最大流会超时。
于是我们可以优化建图。
我们建立新点
i
′
i'
i′ 的目的,其实是要使得存在这么一个点,通过若干容量为无穷的边,可以只到达所有符合
1
≤
j
<
i
,
l
i
≤
a
j
≤
r
i
1\leq j<i,l_i\leq a_j\leq r_i
1≤j<i,li≤aj≤ri 的
j
j
j。但是,不同的
i
′
i'
i′ ,可能连向一大批相同的
j
j
j ,
**
j
j
j 和
a
j
a_j
**
aj 都是连续在一个范围内的。
瞎扯了这么多,我也不绕弯了,用线段树优化建图。每次的
i
′
i'
i′ 只需要连向线段树上的某些(log的数量级)区间点,每个父亲向左右儿子连容量无穷的边,每个叶子向
a
j
a_j
aj 等于某一值的所有
j
j
j 连容量无穷的边。
有两个条件,
1
≤
j
<
i
1\leq j<i
1≤j<i 和
l
i
≤
a
j
≤
r
i
l_i\leq a_j\leq r_i
li≤aj≤ri ,难道要树套树?
其实只用可持久化线段树就行了。
n
≤
5000
n\leq 5000
n≤5000 ,貌似有点小?根号和 log 差不太多啊。
可持久化分块,何如?每次只用新建 1~2 个点,边数也不用如此繁多。
实际上比线段树优秀得多:
线段树
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 5005
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define eps (1e-4)
#define SI(x) set<x>::iterator
#define MI map<int,int>::iterator
#define SQ 51
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x) return ;
putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
if(!x) putchar('0');
else if(x < 0) putchar('-'),putpos(-x);
else putpos(x);
}
void AIput(LL x,char c) {putnum(x);putchar(c);}
int n,m,s,o,k;
int cnp,hd[MAXN*200],S,T;
int v[MAXN*400],nx[MAXN*400],rev[MAXN*400],cne;
LL w[MAXN*400];
int ins(int x,int y,LL k) {
if(!x || !y) return 0;
nx[++ cne] = hd[x];v[cne] = y;w[cne] = k;hd[x] = cne;
nx[++ cne] = hd[y];v[cne] = x;w[cne] = 0;hd[y] = cne;
rev[cne] = cne-1; rev[cne-1] = cne; return cne-1;
}
int hd2[MAXN*200],d[MAXN*200];
bool bfs(int S,int T) {
for(int i = 1;i <= cnp;i ++) {
hd2[i] = hd[i]; d[i] = -1;
}
queue<int> b;
d[S] = 0;
b.push(S);
while(!b.empty()) {
int t = b.front();b.pop();
if(t == T) return 1;
for(int i = hd[t];i;i = nx[i]) {
if(d[v[i]] < 0 && w[i] > 0) {
d[v[i]] = d[t] + 1;
b.push(v[i]);
}
}
}
return 0;
}
LL dfs(int x,LL flow) {
if(x == T) return flow;
LL res = 0;
for(int i = hd2[x];i;i = nx[i]) {
if(d[v[i]] == d[x] + 1 && w[i] > 0) {
LL mx = dfs(v[i],min(flow-res,w[i]));
res += mx; w[i] -= mx; w[rev[i]] += mx;
if(res == flow) break;
}
hd2[x] = nx[i];
}
return res;
}
LL dinic(int S,int T) {
LL ans = 0;
while(bfs(S,T)) {
ans += dfs(S,(LL)1e18);
}return ans;
}
int A[MAXN],bk[MAXN],we[MAXN],ll[MAXN],rr[MAXN],P[MAXN];
int ar[MAXN];
int tre[MAXN<<2],M;
void maketree(int n) {
M=1;while(M<n+2)M<<=1;
}
void addtree(int x,int y) {
int s=M+x;ins(++ cnp,tre[s],(LL)1e18);
tre[s] = cnp;ins(tre[s],y,(LL)1e18);s >>= 1;
while(s) {
tre[s] = ++ cnp;
ins(tre[s],tre[s<<1],(LL)1e18);
ins(tre[s],tre[s<<1|1],(LL)1e18);
s >>= 1;
}return ;
}
int buildp(int l,int r) {
int p = ++ cnp;
int s = M+l-1,t = M+r+1;
while(s || t) {
if((s>>1) ^ (t>>1)) {
if(!(s&1)) ins(p,tre[s^1],(LL)1e18);
if(t & 1) ins(p,tre[t^1],(LL)1e18);
}else break;
s >>= 1;t >>= 1;
}return p;
}
int main() {
n = read();
cnp = n+2; S = n+1; T = n+2;
LL ans = 0;
for(int i = 1;i <= n;i ++) {
A[i] = read(); ar[i] = A[i];
bk[i] = read(); we[i] = read();
ll[i] = read(); rr[i] = read();
P[i] = read();
ins(S,i,bk[i]); ins(i,T,we[i]);
ans += we[i]+bk[i];
}
sort(ar + 1,ar + 1 + n);
for(int i = 1;i <= n;i ++) {
A[i] = lower_bound(ar + 1,ar + 1 + n,A[i]) - ar;
ll[i] = lower_bound(ar + 1,ar + 1 + n,ll[i]) - ar;
rr[i] = lower_bound(ar + 1,ar + 1 + n,rr[i]+1) - ar - 1;
}
maketree(n);
for(int i = 1;i <= n;i ++) {
int p = buildp(ll[i],rr[i]);
ins(i,p,P[i]);
addtree(A[i],i);
}
ans -= dinic(S,T);
AIput(ans,'\n');
// for(int i = 1;i <= n;i ++) {
// printf("%d(%d): ",i,A[i]);
// if(w[fr[i]] > 0) {
// printf("black");
// }
// else printf("white");
// printf(" [%d,%d]\n",ll[i],rr[i]);
// }
return 0;
}
分块
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 5005
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define eps (1e-4)
#define SI(x) set<x>::iterator
#define MI map<int,int>::iterator
#define SQ 51
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x) return ;
putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
if(!x) putchar('0');
else if(x < 0) putchar('-'),putpos(-x);
else putpos(x);
}
void AIput(LL x,char c) {putnum(x);putchar(c);}
int n,m,s,o,k;
int cnp,hd[MAXN*200],S,T;
int v[MAXN*400],nx[MAXN*400],rev[MAXN*400],cne;
LL w[MAXN*400];
int ins(int x,int y,LL k) {
if(!x || !y) return 0;
nx[++ cne] = hd[x];v[cne] = y;w[cne] = k;hd[x] = cne;
nx[++ cne] = hd[y];v[cne] = x;w[cne] = 0;hd[y] = cne;
rev[cne] = cne-1; rev[cne-1] = cne; return cne-1;
}
int hd2[MAXN*200],d[MAXN*200];
bool bfs(int S,int T) {
for(int i = 1;i <= cnp;i ++) {
hd2[i] = hd[i]; d[i] = -1;
}
queue<int> b;
d[S] = 0;
b.push(S);
while(!b.empty()) {
int t = b.front();b.pop();
if(t == T) return 1;
for(int i = hd[t];i;i = nx[i]) {
if(d[v[i]] < 0 && w[i] > 0) {
d[v[i]] = d[t] + 1;
b.push(v[i]);
}
}
}
return 0;
}
LL dfs(int x,LL flow) {
if(x == T) return flow;
LL res = 0;
for(int i = hd2[x];i;i = nx[i]) {
if(d[v[i]] == d[x] + 1 && w[i] > 0) {
LL mx = dfs(v[i],min(flow-res,w[i]));
res += mx; w[i] -= mx; w[rev[i]] += mx;
if(res == flow) break;
}
hd2[x] = nx[i];
}
return res;
}
LL dinic(int S,int T) {
LL ans = 0;
while(bfs(S,T)) {
ans += dfs(S,(LL)1e18);
}return ans;
}
int bl[MAXN],cnb,tt[MAXN];
int A[MAXN],bk[MAXN],we[MAXN],ll[MAXN],rr[MAXN],P[MAXN];
int ar[MAXN];
int buildp(int l,int r) {
int s = l/SQ+1,t = r/SQ+1;
int p = ++ cnp;
if(s == t) {
for(int i = l;i <= r;i ++) ins(p,tt[i],(LL)1e18);
}
else {
for(int i = l;(i/SQ+1) == s;i ++) ins(p,tt[i],(LL)1e18);
for(int i = r;(i/SQ+1) == t;i --) ins(p,tt[i],(LL)1e18);
for(int i = s+1;i < t;i ++) {
ins(p,bl[i],(LL)1e18);
}
}return p;
}
int main() {
n = read();
cnp = n+2; S = n+1; T = n+2;
LL ans = 0;
for(int i = 1;i <= n;i ++) {
A[i] = read(); ar[i] = A[i];
bk[i] = read(); we[i] = read();
ll[i] = read(); rr[i] = read();
P[i] = read();
ins(S,i,bk[i]); ins(i,T,we[i]);
ans += we[i]+bk[i];
}
sort(ar + 1,ar + 1 + n);
for(int i = 1;i <= n;i ++) {
A[i] = lower_bound(ar + 1,ar + 1 + n,A[i]) - ar;
ll[i] = lower_bound(ar + 1,ar + 1 + n,ll[i]) - ar;
rr[i] = lower_bound(ar + 1,ar + 1 + n,rr[i]+1) - ar - 1;
}
for(int i = 1;i <= n;i ++) {
int p = buildp(ll[i],rr[i]);
ins(i,p,P[i]);
int B = A[i]/SQ+1; cnb = max(cnb,B);
ins(++ cnp,bl[B],(LL)1e18);
bl[B] = cnp;
ins(bl[B],i,(LL)1e18);
ins(++ cnp,tt[A[i]],(LL)1e18);
tt[A[i]] = cnp;
ins(tt[A[i]],i,(LL)1e18);
}
ans -= dinic(S,T);
AIput(ans,'\n');
// for(int i = 1;i <= n;i ++) {
// printf("%d(%d): ",i,A[i]);
// if(w[fr[i]] > 0) {
// printf("black");
// }
// else printf("white");
// printf(" [%d,%d]\n",ll[i],rr[i]);
// }
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章