3218: a + b Problem
Time Limit: 20 Sec Memory Limit: 40 MBSubmit: 1322 Solved: 500
[Submit][Status][Discuss]
Description
.jpg)
.jpg)
Input
Output
Sample Input
Sample Output
HINT
Source
分析：
首先我们可以发现这可以用最小割解决...因为要最大化结果，所以用总价值减去最小割...
一开始想了一个错误的建图...
把每个点拆成i和i'，从S向i连一条bi的边，从i'向T连一条wi的边，从i到i'连一条pi的边，所以如果割bi代表选白色，割wi代表选黑色，然后对于奇怪的格子i我们从i'向j连一条容量位inf的边...
如果这样建我们会发现当i为奇怪的格子的时候，割的时候会割掉min(pi,pj)而不是pi，所以我们应该从i向T连一条wi的边而不是从i'向T连一条wi的边...
现在我们的边数是$O(n^{2})$的...这样会被卡的很惨...
现在我们考虑每一个i’会连出$O(n)$条边，这些边所对应的j的权值aj是属于li~ri这个区间的，所以我们可以用线段树维护区间，把i连向代表li~ri这个区间的节点...然后对于每一个ai，我们把代表ai的节点连向对应的i...
但是这样我们就无法满足j<i这个条件，所以我们要保留历史版本，所以我们需要用可持久化线段树维护这些边...
这样我们就可以把边数和点数都变成$O(nlgn)$...
需要注意的是对于每一个叶子结点ai我们需要从新版本的ai向旧版本的ai连边...(因为可能有好多个j的a值都是相同的...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=100000+5,maxm=700000+5;
int n,S,T,ans,cnt,len,q[maxm],a[maxn],b[maxn],w[maxn],p[maxn],ll[maxn],rr[maxn],mp[maxn<<1],hd[maxn],fl[maxm],to[maxm],nxt[maxm],pos[maxn];
inline void add(int x,int y,int z){
fl[cnt]=z;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
fl[cnt]=0;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;
}
namespace PSTree{
int tot=0,ls[maxm],rs[maxm],root[maxn];
inline void change(int l,int r,int x,int &y,int pos,int id){
y=++tot;
if(l==r){
add(2*n+y,id,inf);
if(x)
add(2*n+y,2*n+x,inf);
return;
}
int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];
if(pos<=mid)
change(l,mid,ls[x],ls[y],pos,id);
else
change(mid+1,r,rs[x],rs[y],pos,id);
if(ls[y])
add(2*n+y,2*n+ls[y],inf);
if(rs[y])
add(2*n+y,2*n+rs[y],inf);
}
inline void query(int l,int r,int L,int R,int x,int id){
if(!x)
return;
if(l==L&&r==R){
add(id,2*n+x,inf);
return;
}
int mid=(l+r)>>1;
if(R<=mid)
query(l,mid,L,R,ls[x],id);
else if(L>mid)
query(mid+1,r,L,R,rs[x],id);
else
query(l,mid,L,mid,ls[x],id),query(mid+1,r,mid+1,R,rs[x],id);
}
}using namespace PSTree;
inline bool bfs(void){
memset(pos,-1,sizeof(pos));
int head=0,tail=0;
q[0]=S;pos[S]=0;
while(head<=tail){
int top=q[head++];
for(int i=hd[top];i!=-1;i=nxt[i])
if(pos[to[i]]==-1&&fl[i])
pos[to[i]]=pos[top]+1,q[++tail]=to[i];
}
return pos[T]!=-1;
}
inline int find(int v,int f){
if(v==T)
return f;
int res=0,t;
for(int i=hd[v];i!=-1&&f>res;i=nxt[i])
if(pos[to[i]]==pos[v]+1&&fl[i])
t=find(to[i],min(f-res,fl[i])),res+=t,fl[i]-=t,fl[i^1]+=t;
if(!res)
pos[v]=-1;
return res;
}
inline int dinic(void){
int res=0,t;
while(bfs())
while(t=find(S,inf))
res+=t;
return res;
}
signed main(void){
scanf("%d",&n);len=0;
memset(hd,-1,sizeof(hd));
for(int i=1;i<=n;i++)
scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&ll[i],&rr[i],&p[i]),mp[++len]=a[i],mp[++len]=ll[i],mp[++len]=rr[i];
sort(mp+1,mp+len+1);len=unique(mp+1,mp+len+1)-mp-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(mp+1,mp+len+1,a[i])-mp,ll[i]=lower_bound(mp+1,mp+len+1,ll[i])-mp,rr[i]=lower_bound(mp+1,mp+len+1,rr[i])-mp,
PSTree::change(1,len,root[i-1],root[i],a[i],i),PSTree::query(1,len,ll[i],rr[i],root[i-1],i+n);
T=2*n+tot+1;ans=0;S=0;
for(int i=1;i<=n;i++)
add(S,i,b[i]),add(i,T,w[i]),add(i,i+n,p[i]),ans+=w[i]+b[i];
printf("%d
",ans-dinic());
return 0;
}
//rncqjtdxjg
By NeighThorn