【主席树优化网络流】A+B Problem

主席树, 网络流

传送机：UOJ77

这道题可能真特么和a+b没什么关系

思路：

  • 连s->i,cap=$b_i$;连i->t,cap=$w_i$;

  • 如果没有$p_i$这样连边以后最小割就是答案

  • 然而有$p_i$，如果直接把满足条件的i向j连边就会重复计算

  • 所以新建一个i的替身i'

  • 把i向i'连一条长度为$p_i$的边，再把i'连向相应的j，这样$p_i$就不会重复计算了

  • 由于直接连边边数太多，肯定会GG，

  • 如果不考虑下标限制，只考虑权值限制，那么连边一定是连续的，用线段树优化连边

  • 再考虑下标限制，只要依次加入每个点，用主席树即可

注意：

  • 主席树的要修改的叶子结点要继承上一状态的叶子结点再连边
  • 因为同一权值的点可能很多
  • 另外离散化以后会变快（边数会变少），虽然我懒得写了

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 400030
#define M 1000000030
#define INF 0x7fffffff
int n,s,t,a,b,w,l,r,p,tot,tot_edge,ans,head[N],iter[N],level[N],q[N],rt[N],ls[N],rs[N];
struct edge{int v,cap,rev,nxt;}e[N*8];
void add(int x,int y,int cap){
	e[++tot_edge].v=y; e[tot_edge].cap=cap; e[tot_edge].rev=tot_edge+1; e[tot_edge].nxt=head[x]; head[x]=tot_edge;
	e[++tot_edge].v=x; e[tot_edge].cap=0; e[tot_edge].rev=tot_edge-1; e[tot_edge].nxt=head[y]; head[y]=tot_edge;
}
void bfs(int s){
	int tt=0,ww=1; level[s]=0; q[1]=s;
	while (tt<ww){
		int v=q[++tt];
		for (int i=head[v];i;i=e[i].nxt){
			edge &E=e[i];
			if (E.cap>0 && level[E.v]<0){
				level[E.v]=level[v]+1; q[++ww]=E.v;
			}
		}
	}
}
int dfs(int v,int t,int f){
	if (v==t) return f;
	for (int &i=iter[v];i;i=e[i].nxt){
		edge &E=e[i];
		if (E.cap>0 && level[E.v]>level[v]){
			int ff=dfs(E.v,t,min(f,E.cap));
			if (ff>0){E.cap-=ff; e[E.rev].cap+=ff; return ff;}
		}
	}
	return 0;
}
int dinic(int s,int t){
	int flow=0;
	for (;;){
		memset(level,-1,sizeof level); bfs(s);
		if (level[t]<0) return flow;
		for (int i=s;i<=t;i++) iter[i]=head[i];
		int f=0;
		while ((f=dfs(s,t,INF))>0) flow+=f;
	}
}
void ins(int &root,int root2,int l,int r,int k){
	if (!root){root=++tot;}
	if (l==r){add(root,root2,INF); add(root,k,INF); return;}//不要忘了继承上一状态的叶子结点 
	int mid=(l+r)>>1;
	if (a<=mid){
		rs[root]=rs[root2]; ins(ls[root],ls[root2],l,mid,k);
		if (ls[root]) add(root,ls[root],INF); if (rs[root]) add(root,rs[root],INF);
	}
	if (a>mid){
		ls[root]=ls[root2]; ins(rs[root],rs[root2],mid+1,r,k);
		if (ls[root]) add(root,ls[root],INF); if (rs[root]) add(root,rs[root],INF);
	}
}
void link(int root,int l,int r,int L,int R,int k){
	if (!root) return;
	if (L<=l && R>=r){add(k,root,INF); return;}
	int mid=(l+r)>>1;
	if (L<=mid) link(ls[root],l,mid,L,R,k);
	if (R>mid) link(rs[root],mid+1,r,L,R,k);
}
int main(){
	scanf("%d",&n);
	s=0; t=n*60+1; tot=n*2;
	for (int i=1;i<=n;i++){
		scanf("%d%d%d%d%d%d",&a,&b,&w,&l,&r,&p); ans+=b+w; a++; l++; r++;//权值可能为0 
		add(s,i,b); add(i,t,w); add(i,i+n,p);
		link(rt[i-1],1,M,l,r,i+n); ins(rt[i],rt[i-1],1,M,i);
	}
	
	printf("%d\n",ans-dinic(s,t));
}