3218: a + b Problem
Time Limit: 20 Sec Memory Limit: 40 MBSubmit: 2229 Solved: 836
[Submit][Status][Discuss]
Description
.jpg)
.jpg)
Input
Output
Sample Input
10
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
5 6 7 1 1 2
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
5 6 7 1 1 2
Sample Output
55
HINT
Source
此题是一个选择性问题，明显是用网络流来解决。
考虑没有p限制，这是一个最大权闭合子图问题。
从S像每一个i连一条bi的边，从i向T连一条wi的边，跑最小割即可。
对于p限制，我们要体现出要是没割wi且存在一个aj使得他在li-ri之间，他就要变得奇怪。
所以我们可以将i拆成两个点i，i+n。
从i向i+n连一条容量为pi的边，从i+n向每一个满足条件的j连一条inf的边。
由于n为5000，考虑使用主席树优化建图即可解决。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<cmath> 6 #include<algorithm> 7 #define maxm 1000005 8 #define maxn 5005 9 #define inf 999999999 10 using namespace std; 11 inline int read() { 12 int x=0,f=1;char ch=getchar(); 13 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; 14 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; 15 return x*f; 16 } 17 int ans=0,n; 18 struct Edge {int to,nxt,c;}e[maxm*2]; 19 int head[maxn*20],cnt; 20 inline void add(int u,int v,int c) {e[cnt].nxt=head[u];e[cnt].to=v;e[cnt].c=c;head[u]=cnt++;swap(u,v);c=0;e[cnt].nxt=head[u];e[cnt].to=v;e[cnt].c=c;head[u]=cnt++;} 21 int a[maxn],b[maxn],w[maxn],l[maxn],r[maxn],p[maxn],hsh[maxn*20],sum; 22 int S,T,sz; 23 struct seg {int l,r;}t[maxn*20]; 24 int rt[maxn*20]; 25 inline void query(int l,int r,int x,int L,int R,int point) { 26 if(!x||L>r||R<l) return; 27 if(L<=l&&R>=r) {add(point,x,inf);return;} 28 int mid=(l+r)>>1; 29 if(L<=mid) query(l,mid,t[x].l,L,R,point); 30 if(R>mid) query(mid+1,r,t[x].r,L,R,point); 31 return; 32 } 33 inline void insert(int l,int r,int &x,int pre,int pos,int point) { 34 x=++sz; 35 if(l==r&&pre>0) add(x,pre,inf); 36 if(l==r) {add(x,point,inf);return;} 37 t[x]=t[pre]; 38 int mid=(l+r)>>1; 39 if(pos<=mid) insert(l,mid,t[x].l,t[pre].l,pos,point); 40 else insert(mid+1,r,t[x].r,t[pre].r,pos,point); 41 if(t[x].l) add(x,t[x].l,inf); 42 if(t[x].r) add(x,t[x].r,inf); 43 } 44 int q[maxn*20],dis[maxn*20]; 45 inline bool bfs() { 46 for(int i=0;i<=sz;i++) dis[i]=-100000000; 47 int hd=0,tl=1; 48 q[0]=T;dis[T]=0; 49 while(hd!=tl) { 50 int now=q[hd++];if(hd==100000) hd=0; 51 for(int i=head[now];i>=0;i=e[i].nxt) { 52 int to=e[i].to;if(dis[to]>-100000000||!e[i^1].c) continue; 53 dis[to]=dis[now]-1;q[tl++]=to; 54 if(tl==100000) tl=0; 55 } 56 } 57 return dis[S]>-100000000; 58 } 59 inline int dfs(int x,int mxf) { 60 if(!mxf||x==T) return mxf; 61 int nf=0; 62 for(int i=head[x];i>=0;i=e[i].nxt) { 63 int to=e[i].to; 64 if(e[i].c&&dis[to]==dis[x]+1) { 65 int f=dfs(to,min(mxf,e[i].c)); 66 mxf-=f;e[i].c-=f; 67 e[i^1].c+=f;nf+=f; 68 if(!mxf) break; 69 } 70 } 71 if(!nf) dis[x]=-100000000; 72 return nf; 73 } 74 inline void dinic() {while(bfs()) ans-=dfs(S,inf);} 75 int main() { 76 memset(head,-1,sizeof(head)); 77 n=read();S=2*n+1,T=2*n+2;sz=T; 78 for(int i=1;i<=n;i++) { 79 a[i]=read(),b[i]=read(),w[i]=read(),l[i]=read(),r[i]=read(),p[i]=read(); 80 hsh[++sum]=a[i];hsh[++sum]=l[i];hsh[++sum]=r[i]; 81 ans+=w[i]+b[i]; 82 } 83 sort(hsh+1,hsh+sum+1);sum=unique(hsh+1,hsh+sum+1)-hsh-1; 84 for(int i=1;i<=n;i++) { 85 a[i]=lower_bound(hsh+1,hsh+sum+1,a[i])-hsh; 86 l[i]=lower_bound(hsh+1,hsh+sum+1,l[i])-hsh; 87 r[i]=lower_bound(hsh+1,hsh+sum+1,r[i])-hsh; 88 add(S,i,b[i]);add(i,i+n,p[i]);add(i,T,w[i]); 89 } 90 for(int i=1;i<=n;i++) { 91 if(i>1) query(1,sum,rt[i-1],l[i],r[i],i+n); 92 insert(1,sum,rt[i],rt[i-1],a[i],i); 93 } 94 dinic();printf("%d ",ans); 95 }