Lvat_s Blog

这是一个卡内存的悲伤故事

我把UOJ爆了一通才卡完内存，然后又发现在BZOJ上MLE了

然后又是乱卡一通，终于A掉了

题解(PoPoQQQ)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF=2100000000,N=900005;

int n,en,S,T,level[N],h[N],cur[N],his[5005],cnt,flow_cnt,ans;
queue<int> Q;

struct Edge{
int b,f,back,next;
}e[N];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(!e[i].f || level[v])continue;
		level[v]=level[u]+1;
		Q.push(v);
    }
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
    if(e[i].f && level[v]==level[u]+1 && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(f==0)return flow;
    }
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=flow_cnt;i++)cur[i]=h[i];ans+=DFS(S,2100000000);}
return ans;
}

struct SegTree{
int nl,nr,v,pos;
}tree[N];

void Newnode(int &rt,int lastrt){
rt=++cnt;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
tree[rt].pos=++flow_cnt;
}

void Update(int &rt,int lastrt,int l,int r,int pos,int val){
Newnode(rt,lastrt);
int mid=l+r>>1;
AddEdge(val,tree[rt].pos,INF);
if(lastrt)AddEdge(tree[lastrt].pos,tree[rt].pos,INF);
if(l==r)return;
if(pos<=mid)Update(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val);
if(pos>mid)Update(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val);
}

void Query(int rt,int l,int r,int x,int y,int point){
if(!rt)return;
if(x<=l && r<=y){AddEdge(tree[rt].pos,point,INF);return;}
int mid=l+r>>1;
if(x<=mid)Query(tree[rt].nl,l,mid,x,y,point);
if(y>mid)Query(tree[rt].nr,mid+1,r,x,y,point);
}

int main(){
freopen("3218.in","r",stdin);
freopen("3218.out","w",stdout);
scanf("%d",&n);
S=n*2+1;T=n*2+2;flow_cnt=n*2+2;
for(int i=1;i<=n;i++){
	int a,b,w,l,r,p;
    scanf("%d %d %d %d %d %d",&a,&b,&w,&l,&r,&p);
    ans+=b+w;
    AddEdge(S,i+n,w);AddEdge(i+n,T,b);
    AddEdge(i,i+n,p);
    Update(his[i],his[i-1],0,1000000000,a,i+n);
    Query(his[i-1],0,1000000000,l,r,i);
}
printf("%d\n",ans-Dinic());
return 0;
}