3800. [JZOI 2022 day1]铁山靠

【题目描述】

铁山靠是 $\rm ikun$ 的必备技能。坤坤现在给你一个 $n+2$ 个点的图，编号 $0$ 到 $n+1$ ，其中 $0$ 号点是源点，$n+1$ 号点是汇点，图中有若干条有向管道，只有在你求出这个图的最大流后，坤坤才会教你铁山靠。

你苦苦思考了两年半还是解决不出来，于是坤坤降低难度，把管道减少到 $3n$ 条，其中有 $n$ 条是源点连向 $1$ 到 $n$ 之间的点的，流量为 $a_i$；另外 $n$ 条从 $1$ 到 $n$ 连向汇点，流量为 $b_i$ ；还有 $n$ 条形如 $i$ 连向 $p_i(p_i ≠ i)$ ，流量为 $c_i$。

为了证明自己不是小黑子，你誓要学会铁山靠。

【输入格式】

第一行一个整数 $n$。

接下来四行每行 $4$ 个整数，分别表示$p_i,\ a_i,\ b_i,\ c_i$。

【输出格式】

一行一个整数表示答案。

【样例1输入】

5 3
3 1 3 3 3
4 2 2 5 5
2 4 2 1 2
2 3 2 2 4

【样例1输出】

9

【样例2/3输入输出】

点击下载样例2/3和dinic程序 

【数据规模与约定】

本题采取子任务捆绑测试。

对于所有数据，$2 \leq n \leq 10^6 ，1 \leq p_i \leq n，1 \leq a_i,b_i,c_i \leq 10^9$。

$\rm sub1(5pts)$: $n \leq 10$。

$\rm sub2(10pts)$: $n \leq 5000$。

$\rm sub3(15pts)$: 保证 $p_i$ 随机生成。

$\rm sub4(20pts)$: 若把图中边看做无向边，保证不存在两点无法通过 $i$ 与 $p_i$ 形式的边直接或间接联通。

$\rm sub5(50pts)$: 无特殊限制。

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.22 pro4