题解51nod2564 格子染色

题解51nod2564 格子染色

题面

51nod

解析

考虑一个网络流做法.

先不考虑 $p_i$ 的影响,那么我们把每个点向源点连边,容量为 $w_i$,再向汇点连边,容量为 $b_i$,跑最小割即可.

然后考虑 $p_i$,对于点 $i$ 我们可以拆出一个点 $i’$,并将满足条件的 $j$ 向 $i’$ 连边,容量为 $\inf$,再将 $i’$ 向 $i$ 连边,容量为 $p_i$,继续跑最小割即可.

但是这样做边数太多,但是考虑到对于一个点 $i$ 合法的 $j$ 都在一个区间里,

所以可以对每个点建一棵权值线段树,将 $j$ 向 $a_j$ 对应的叶子节点连边,再将根节点向 $i$ 连边.

由于每个 $i$ 只会插入一次,用可持久化线段树即可.

code

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=5005;
const int M=2000005;
const int INF=0x3f3f3f3f;
struct node{int l,r,a,b,w,p;}a[N];
struct tree{int ls,rs;}t[M];
int n,tot,c[N],rt[N];

namespace network{
struct edge{int to,next,v;}e[M];
int head[M],cnt=1;
int d[M],cur[M],S,T;
queue<int> que;
inline void add(int x,int y,int v){
e[++cnt]=(edge){head[x],y,v};head[x]=cnt;
e[++cnt]=(edge){head[y],x,0};head[y]=cnt;
}
inline bool bfs(){
memset(d,0,sizeof(d));
memcpy(cur,head,sizeof(cur));
que.push(S);d[S]=1;
while(!que.empty()){
int x=que.front();que.pop();
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(d[k]||!e[i].v) continue;
d[k]=d[x]+1;que.push(k);
}
}
return d[T];
}
inline int dfs(int x,int mi){
if(x==T||!mi) return mi;
int flow=0;
for(int &i=cur[x];i;i=e[i].to){
int k=e[i].next;
if(!e[i].v||d[k]!=d[x]+1) continue;
int ret=dfs(k,min(mi,e[i].v));
e[i].v-=ret;e[i^1].v+=ret;
mi-=ret;flow+=ret;
if(!mi) break;
}
if(mi) d[x]=-1;
return flow;
}
inline ll DINIC(){
ll ans=0;
while(bfs()) ans+=dfs(S,INF);
return ans;
}
}
using namespace network;

inline void insert(int o,int &p,int x,int v,int l,int r){
p=++tot;t[p]=t[o];
add(o,p,INF);
if(l==r){add(x,p,INF);return ;}
int mid=(l+r)>>1;
if(v<=mid) insert(t[o].ls,t[p].ls,x,v,l,mid),add(t[p].ls,p,INF);
else insert(t[o].rs,t[p].rs,x,v,mid+1,r),add(t[p].rs,p,INF);
}

inline void addedge(int p,int x,int l,int r,int pl,int pr){
if(!p) return ;
if(pl>=l&&pr<=r){
add(p,x,INF);return ;
}
int mid=(pl+pr)>>1;
if(l<=mid) addedge(t[p].ls,x,l,r,pl,mid);
if(r>mid) addedge(t[p].rs,x,l,r,mid+1,pr);
}

int main(){
n=read();S=n*2+1;T=S+1,tot=T+1;
for(int i=1;i<=n;i++)
a[i].a=read(),a[i].b=read(),a[i].w=read(),a[i].l=read(),a[i].r=read(),a[i].p=read();
for(int i=1;i<=n;i++) c[i]=a[i].a;
sort(c+1,c+n+1);int m=unique(c+1,c+n+1)-c-1;
ll ans=0;
for(int i=1;i<=n;i++){
ans+=a[i].b+a[i].w;
add(S,i,a[i].w);add(i,T,a[i].b);
}
for(int i=1;i<=n;i++){
add(i+n,i,a[i].p);
int l=lower_bound(c+1,c+m+1,a[i].l)-c;
int r=upper_bound(c+1,c+m+1,a[i].r)-c-1;
if(l<=r) addedge(rt[i-1],i+n,l,r,1,m);
l=lower_bound(c+1,c+m+1,a[i].a)-c;
insert(rt[i-1],rt[i],i,l,1,m);
}
ans-=DINIC();
printf("%lld\n",ans);
return 0;
}
感谢您又打赏