首页 > 代码库 > BZOJ 3218 a + b Problem 可持久化线段树+最小割
BZOJ 3218 a + b Problem 可持久化线段树+最小割
题目大意:。。。自己看
从源点出发,分别向汇点连两条流量为a和b的边,跑最大流即是a+b。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10 #define S 1 #define T 2 #define INF 0x3f3f3f3f using namespace std; struct abcd{ int to,f,next; }table[100]; int head[M],tot=1; void Add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } void Link(int x,int y,int z) { Add(x,y,z); Add(y,x,0); } namespace Max_Flow{ int dpt[M]; bool BFS() { static int q[M]; int i,r=0,h=0; memset(dpt,-1,sizeof dpt); q[++r]=S;dpt[S]=1; while(r!=h) { int x=q[++h]; for(i=head[x];i;i=table[i].next) if(table[i].f&&!~dpt[table[i].to]) { dpt[table[i].to]=dpt[x]+1; q[++r]=table[i].to; if(table[i].to==T) return true; } } return false; } int Dinic(int x,int flow) { int i,left=flow; if(x==T) return flow; for(i=head[x];i&&left;i=table[i].next) if(table[i].f&&dpt[table[i].to]==dpt[x]+1) { int temp=Dinic(table[i].to,min(left,table[i].f) ); if(!temp) dpt[table[i].to]=-1; left-=temp; table[i].f-=temp; table[i^1].f+=temp; } return flow-left; } } int main() { using namespace Max_Flow; int i,x,ans=0; for(i=1;i<=2;i++) scanf("%d",&x),Link(S,T,x); while( BFS() ) ans+=Dinic(S,INF); cout<<ans<<endl; return 0; }
。。。上面那个是开玩笑的
首先考虑朴素一些的做法
将每个点i拆成两个点i和i‘,i‘向i连一条流量为p的边
从S向i连一条流量为w的边 从i向T连一条流量为b的边
如果j选白点i选黑点时i会变得奇♂怪起来的话,就从j到i‘连一条流量为INF的边
这样就保证了如果j选择了白色,i就要么选择白色,要么变得奇♂怪
但是这样建图的话,j->i‘的边数可以达到O(n^2)
我们可以考虑建一棵权值线段树,从j向相应叶节点连边,从i‘覆盖的区间向i’连边
但是这样做我们无视了j<i这个条件
因此我们将这棵线段树改成可持久化线段树即可
每新建一条链,从旧版本的每个点和点i分别向新建的链上节点连边
然后去上一个版本查询相应区间并连边即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 200200 #define S 0 #define T 200199 #define INF 0x3f3f3f3f #define P1(x) ((x)*2-1) #define P2(x) ((x)<<1) using namespace std; int n,m,cnt; long long ans; namespace Max_Flow{ struct abcd{ int to,f,next; }table[1001001]; int head[M],tot=1; int dpt[M]; void Add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } void Link(int x,int y,int z) { Add(x,y,z); Add(y,x,0); } bool BFS() { static int q[M]; int i,r=0,h=0; memset(dpt,-1,sizeof dpt); dpt[S]=1;q[++r]=S; while(r!=h) { int x=q[++h]; for(i=head[x];i;i=table[i].next) if(table[i].f&&!~dpt[table[i].to]) { dpt[table[i].to]=dpt[x]+1; q[++r]=table[i].to; if(table[i].to==T) return true; } } return false; } int Dinic(int x,int flow) { int i,left=flow; if(x==T) return flow; for(i=head[x];i&&left;i=table[i].next) if(table[i].f&&dpt[table[i].to]==dpt[x]+1) { int temp=Dinic(table[i].to,min(left,table[i].f) ); left-=temp; table[i].f-=temp; table[i^1].f+=temp; } if(left) dpt[x]=-1; return flow-left; } void DFS(int x) { static int v[M]; v[x]=1; if(x<=n<<1) printf("%d\n",x+1>>1); for(int i=head[x];i;i=table[i].next) if(table[i].f&&!v[table[i].to]) DFS(table[i].to); } void Debug() { static int s[M],t[M]; int i; for(i=head[S];i;i=table[i].next) if(table[i].to<=n<<1) s[table[i].to+1>>1]=(table[i].f?-1:1); for(i=head[T];i;i=table[i].next) if(table[i].to<=n<<1) t[table[i].to+1>>1]=(table[i^1].f?-1:1); for(i=1;i<=n;i++) printf("%d %d %d\n",i,s[i],t[i]); puts("--------------------------------------"); DFS(S); puts("--------------------------------------"); for(i=head[P2(6)];i;i=table[i].next) if(table[i].to==P1(6)) cout<<table[i].f<<endl; puts("--------------------------------------"); } } struct Segtree{ Segtree *ls,*rs; int val,num; void* operator new (size_t,Segtree *_,Segtree *__,int ___) { static Segtree mempool[M],*C=mempool; C->ls=_; C->rs=__; C->val=___; C->num=++cnt; return C++; } Segtree* Build_Tree(int x,int y,int pos,int from) { using namespace Max_Flow; int mid=x+y>>1; Segtree *re; if(x==y) re=new (0x0,0x0,val+1) Segtree; else if(pos<=mid) re=new (ls->Build_Tree(x,mid,pos,from),rs,val+1) Segtree; else re=new (ls,rs->Build_Tree(mid+1,y,pos,from),val+1) Segtree; Link(from,re->num,INF); Link(num,re->num,INF); return re; } void Get_Ans(int x,int y,int l,int r,int to) { using namespace Max_Flow; int mid=x+y>>1; if(!val) return ; if(x==l&&y==r) { Link(num,to,INF); return ; } if(r<=mid) ls->Get_Ans(x,mid,l,r,to); else if(l>mid) rs->Get_Ans(mid+1,y,l,r,to); else ls->Get_Ans(x,mid,l,mid,to),rs->Get_Ans(mid+1,y,mid+1,r,to); } }*tree[5050]; int main() { using namespace Max_Flow; int i,a,b,w,l,r,p; cin>>n;cnt=P2(n); tree[0]=new (0x0,0x0,0) Segtree; tree[0]->ls=tree[0]->rs=tree[0]; for(i=1;i<=n;i++) { scanf("%d%d%d%d%d%d",&a,&b,&w,&l,&r,&p); Link(S,P1(i),w); Link(P1(i),T,b); tree[i]=tree[i-1]->Build_Tree(0,1000000000,a,P1(i) ); tree[i-1]->Get_Ans(0,1000000000,l,r,P2(i) ); Link(P2(i),P1(i),p); ans+=w+b; } while( BFS() ) ans-=Dinic(S,INF); //Debug(); cout<<ans<<endl; return 0; }
BZOJ 3218 a + b Problem 可持久化线段树+最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。