生活随笔
收集整理的這篇文章主要介紹了
【BZOJ3218】a+b problem (最小割 + 主席树)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
繼續優化：把a[ ]離散化
#include<bits/stdc++.h>
using namespace std
;
const int inf
=1000000007;
const int N
=200010;
const int M
=1000010;struct Edge{int u
,v
,f
,next
;
}edge
[M
];
int head
[N
],cnt
;
int s
,t
,flow
,level
[N
];struct Node{int x
,id
;
}e
[5010];
int L
[5010],R
[5010],num
,key
[5010],seq
[5010];int tot
,ls
[N
],rs
[N
],rt
[N
],Cnt
[N
];int n
,ans
;void add(int u
,int v
,int f
){edge
[cnt
].u
=u
;edge
[cnt
].v
=v
;edge
[cnt
].f
=f
;edge
[cnt
].next
=head
[u
];head
[u
]=cnt
++;edge
[cnt
].u
=v
;edge
[cnt
].v
=u
;edge
[cnt
].f
=0;edge
[cnt
].next
=head
[v
];head
[v
]=cnt
++;
}
bool bfs(){queue
<int> q
;memset(level
,-1,sizeof(level
));level
[s
]=0;q
.push(s
);while(!q
.empty()){int u
=q
.front();q
.pop();for(int i
=head
[u
];i
!=-1;i
=edge
[i
].next
){int v
=edge
[i
].v
;int f
=edge
[i
].f
;if(f
>0&&level
[v
]<0){level
[v
]=level
[u
]+1;q
.push(v
);}}}return level
[t
]>0;
}
int dfs(int u
,int mx
){if(u
==t
||!mx
) return mx
;int tmp
,res
=0;for(int i
=head
[u
];i
!=-1&&mx
;i
=edge
[i
].next
){int v
=edge
[i
].v
;int f
=edge
[i
].f
;if(level
[v
]==level
[u
]+1&&(tmp
=dfs(v
,min(mx
,f
)))){edge
[i
].f
-=tmp
;edge
[i
^1].f
+=tmp
;res
+=tmp
;mx
-=tmp
;}}if(!res
)level
[u
]=-1;return res
;
}
int dinic(){int maxflow
=0;while(bfs()){maxflow
+=dfs(s
,inf
);}return maxflow
;
}bool cmp(Node x
,Node y
){return x
.x
<y
.x
;
}
int findl(int x
){int l
=1,r
=num
,ans
=num
;while(l
<=r
){int mid
=(l
+r
)/2;if(seq
[mid
]>=x
) ans
=mid
,r
=mid
-1; else l
=mid
+1;}return ans
;
}
int findr(int x
){int l
=1,r
=num
,ans
=1;while(l
<=r
){int mid
=(l
+r
)/2;if(seq
[mid
]<=x
) ans
=mid
,l
=mid
+1; else r
=mid
-1;}return ans
;
}
int modify(int pre
,int l
,int r
,int i
){int now
=++tot
;if(l
==r
){ls
[now
]=rs
[now
]=0;Cnt
[now
]=Cnt
[pre
]+1;}else{int mid
=(l
+r
)/2;if(key
[i
]<=mid
){ls
[now
]=modify(ls
[pre
],l
,mid
,i
);rs
[now
]=rs
[pre
];}else{rs
[now
]=modify(rs
[pre
],mid
+1,r
,i
);ls
[now
]=ls
[pre
];}Cnt
[now
]=Cnt
[ls
[now
]]+Cnt
[rs
[now
]];}add(i
,2*n
+1+now
,inf
);add(2*n
+1+pre
,2*n
+1+now
,inf
);return now
;
}
void query(int o
,int l
,int r
,int i
){if (!Cnt
[o
]) return;if (L
[i
]<=l
&&r
<=R
[i
]){add(2*n
+1+o
,n
+i
,inf
);return;}int mid
=(l
+r
)/2;if(L
[i
]<=mid
) query(ls
[o
],l
,mid
,i
);if(mid
<R
[i
]) query(rs
[o
],mid
+1,r
,i
);
}
int main(){cnt
=0;memset(head
,-1,sizeof(head
));scanf("%d",&n
);s
=0;t
=100000;for(int i
=1;i
<=n
;i
++){int b
,w
,p
;scanf("%d%d%d%d%d%d",&e
[i
].x
,&b
,&w
,&L
[i
],&R
[i
],&p
);e
[i
].id
=i
;ans
+=b
+w
;add(s
,i
,w
);add(i
,t
,b
);add(n
+i
,i
,p
);}sort(e
+1,e
+n
+1,cmp
);num
=1;key
[e
[1].id
]=1;seq
[1]=e
[1].x
;for(int i
=2;i
<=n
;i
++)if(e
[i
].x
==e
[i
-1].x
) key
[e
[i
].id
]=num
;else key
[e
[i
].id
]=++num
,seq
[num
]=e
[i
].x
;tot
=0;rt
[0]=ls
[0]=rs
[0]=0;for(int i
=1;i
<=n
;i
++){L
[i
]=findl(L
[i
]);R
[i
]=findr(R
[i
]);rt
[i
]=modify(rt
[i
-1],1,num
,i
);query(rt
[i
-1],1,num
,i
); }ans
-=dinic();printf("%d\n",ans
); return 0;
}
總結
以上是生活随笔為你收集整理的【BZOJ3218】a+b problem (最小割 + 主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
