P6751: 铁山靠
传统题
2.000s
时间限制
1024MB
内存限制
2 提交
0 解决
【题目描述】
铁山靠是ikun的必备技能。坤坤现在给你一个 n+2 个点的图，编号 0 到 n+1，其中 0 号点是源点，
n+1 号点是汇点，图中有若干条有向管道，只有在你求出这个图的最大流后，坤坤才会教你铁山靠。
你苦苦思考了两年半还是解决不出来，于是坤坤降低难度，把管道减少到 3n 条，其中有 n 条是源点连 向 1 到 n 之间的点的，流量为 ai ；
另外 n 条从1到 n 连向汇点，流量为 bi；还有 n 条形如 i 连向 pi (pi不等于i)，流量为 ci 。
为了证明自己不是小黑子，你誓要学会铁山靠。
【输入格式】
第一行一个整数 n。
接下来四行每行 n 个整数，分别表示 pi,ai,bi,ci。
【输出格式】
一行一个整数表示答案。
【样例】
input1
5
3 3 1 3 3
4 2 2 5 5
2 4 2 1 2
2 3 2 2 4
output1
9
【数据范围】
对于所有数据，2<=n<=1e6，1<=pi<=n，1<=ai,bi,ci<=1e6。
sub1(5pts):n<=10。
sub2(10pts):n<=5000。
sub3(15pts): 保证 pi 随机生成。
sub4(20pts): 若把图中边看做无向边，保证不存在两点无法通过 i 与 pi 形式的边直接或间接联通。
sub5(50pts): 无特殊限制。
【提示】
dinic()算法求解最大流
/*
Dinic Template
author: Displace
language: C-IKUN
*/
#include<bits/stdc++.h>
using namespace std;
#define niganma int
typedef long long haihaiaiyou;
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const niganma N=1e6+5;
niganma n;
niganma chang[N], tiao[N], rap[N], lanqiu[N];
namespace cxk{
niganma caicai, kunkun;
niganma quan[5005], _min[5005], zhi[5005], zuo[5005], ren;
void in(niganma ni, niganma tai, niganma mei){
_min[++ren]=quan[ni]; quan[ni]=ren; zhi[ren]=tai; zuo[ren]=mei;
_min[++ren]=quan[tai]; quan[tai]=ren; zhi[ren]=ni; zuo[ren]=0;
}
niganma q[5005], zuoci, zuoqu, qidai[5005], toupiao[5005];
bool baidai(){
memset(qidai, 0, sizeof qidai);
q[zuoci=zuoqu=1]=caicai; qidai[caicai]=1; toupiao[caicai]=quan[caicai];
while(zuoci<=zuoqu){
niganma ni=q[zuoci++];
for(niganma ji=quan[ni]; ji; ji=_min[ji]){
niganma tai=zhi[ji];
if(zuo[ji]&&!qidai[tai]){
qidai[tai]=qidai[ni]+1; toupiao[tai]=quan[tai];
if(tai==kunkun) return true;
q[++zuoqu]=tai;
}
}
}
return false;
}
haihaiaiyou zhongfen(niganma ni, haihaiaiyou now){
if(ni==kunkun) return now;
haihaiaiyou ret=0;
for(niganma ji=toupiao[ni]; ji&&ret<now; ji=_min[ji]){
niganma tai=zhi[ji], mei=zuo[ji]; toupiao[ni]=ji;
if(mei&&qidai[tai]==qidai[ni]+1){
niganma res=zhongfen(tai, min((haihaiaiyou)mei, now-ret));
if(!res) qidai[tai]=0;
zuo[ji]-=res; zuo[ji^1]+=res; ret+=res;
}
}
return ret;
}
haihaiaiyou dinic(){
haihaiaiyou ret=0, fl;
while(baidai()){
fl=zhongfen(caicai, 1e18);
while(fl) ret+=fl, fl=zhongfen(caicai, 1e18);
}
return ret;
}
void solve(){
caicai=n+1; kunkun=n+2; ren=1;
for(niganma ji=1; ji<=n; ++ji) in(caicai, ji, tiao[ji]);
for(niganma ji=1; ji<=n; ++ji) in(ji, kunkun, rap[ji]);
for(niganma ji=1; ji<=n; ++ji) in(ji, chang[ji], lanqiu[ji]);
dinic();
}
}
niganma main(){
freopen("ikun.in","r",stdin);
freopen("ikun.out","w",stdout);
read(n);
for(niganma ji=1; ji<=n; ++ji) read(chang[ji]);
for(niganma ji=1; ji<=n; ++ji) read(tiao[ji]);
for(niganma ji=1; ji<=n; ++ji) read(rap[ji]);
for(niganma ji=1; ji<=n; ++ji) read(lanqiu[ji]);
cxk::solve();
return 0;
}