BZOJ 3218 a + b Problem 可持久化線段樹+最小割
題目大意：。。。自己看
從源點出發，分別向匯點連兩條流量為a和b的邊，跑最大流即是a+b。
代碼：
#include
#include
#include
#include
#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<
。。。上面那個是開玩笑的
首先考慮樸素一些的做法
將每個點i拆成兩個點i和i'，i'向i連一條流量為p的邊
從S向i連一條流量為w的邊 從i向T連一條流量為b的邊
如果j選白點i選黑點時i會變得奇♂怪起來的話，就從j到i'連一條流量為INF的邊
這樣就保證了如果j選擇了白色，i就要麼選擇白色，要麼變得奇♂怪<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tavKx9Xi0fm9qM28tcS7sKOsai0+aQ=="的邊數可以達到O(n^2)
我們可以考慮建一棵權值線段樹，從j向相應葉節點連邊，從i‘覆蓋的區間向i’連邊
但是這樣做我們無視了j
因此我們將這棵線段樹改成可持久化線段樹即可
每新建一條鏈，從舊版本的每個點和點i分別向新建的鏈上節點連邊
然後去上一個版本查詢相應區間並連邊即可
#include
#include
#include
#include
#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))
coutrs=__;
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<
