2

BZOJ #3681. Arietta

 2 years ago
source link: https://www.shuizilong.com/house/archives/bzoj-3681-arietta/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
July 15, 2022

网络流建模上比上题要简单。
函数式线段树方面需要线段树合并。
总之还是比上一题简单。

darkbzoj 不支持 cpp14，无法方便的使用 atl。。。（至少我不知道怎么改。。。）
值得注意的是对权值重复节点的处理，我们可以在叶子位置动态创建新的节点，
把旧叶子都包含在内，不影响复杂度。

另外对于之前的这类树上线段树合并问题，merge 的时候我们可以破坏掉之前的状态，覆盖式更新而不去 new_node() 以减少内存开支。
但是这个题里我们必须区别出这些状态（建图的时候会 query 到），所以还是老实的每次都 new_node() 为好。。。

const int N = int(1e4) + 9;
struct Network_Flow{
const static int N = int(1e6) + 6, M = 2*N;
int D[N], hd[N], suc[M], to[M], cap[M];
int n, m, s, t;
inline void add_edge(int x, int y, int c){
suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0;
}
inline void add_edgee(int x, int y, int c){
suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = c;
}
#define v to[i]
#define c cap[i]
#define f cap[i^1]
bool bfs(){
static int Q[N]; int cz = 0, op = 1;
fill(D, D+n, 0), D[Q[0] = s] = 1; while (cz < op){
int u = Q[cz++]; REP_G(i, u) if (!D[v]&&c){
D[Q[op++]=v] = D[u]+1;
if (v==t) return 1;
}
}
return 0;
}
LL Dinitz(){
LL z=0; while (bfs()){
static int cur[N], pre[N];
int u=s;pre[s]=-1;cur[s]=hd[s];while (~u){
#define i cur[u]
if (u==t){
int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);
z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;
}
#undef i
int i;for(i=cur[u];i;i=suc[i])if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;}
if (!i)D[u]=0,u=pre[u];
}
}
return z;
}
#undef f
#undef c
#undef v
} G;
int T[N], H[N]; VI adj[N];
int n, m;
namespace Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
const int NN = 100*N;
int c[2][NN]; int tot;
int pp;
int new_node() {
return ++tot;
}
int new_node(int y) {
int x = ++tot; lx = ly; rx = ry;
return x;
}
void Init(int &x, int l = 1, int r = n) {
x = new_node();
if (l == r) {
G.add_edge(x, G.t, 1);
} else {
if (pp < mr) Init(lc);
else Init(rc);
}
}
int Merge(int x, int y, int l = 1, int r = n) {
if (!x || !y) return x | y;
if (l == r) {
int z = new_node();
c[0][z] = x;
c[1][z] = y;
return z;
}
x = new_node(x);
lx = Merge(lx, ly, l, ml);
rx = Merge(rx, ry, mr, r);
return x;
}
void Query(int x, int l, int r, int a, int b, VI& L) {
if (!x || b < l || r < a) return;
if (a <= l && r <= b) {
L.PB(x);
} else {
Query(lc, a, b, L);
Query(rc, a, b, L);
}
}
} using namespace Chairman_Tree;
void dfs(int u = 1) {
pp = H[u]; Init(T[u]);
for (auto v: adj[u]) {
dfs(v);
T[u] = Merge(T[u], T[v]);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, m); G.m = 2; G.s = n+m, G.t = n+m+1; tot = G.t;
FOR_1(i, 2, n) adj[RD()].PB(i);
REP_1(i, n) RD(H[i]); dfs();
REP(i, m) {
int l, r, d; RD(l, r, d); G.add_edge(G.s, i, RD());
VI L; Query(T[d], 1, n, l, r, L);
for (auto l: L) G.add_edge(i, l, INF);
}
FOR_1(x, G.t+1, tot) {
if (lx) G.add_edge(x, lx, INF);
if (rx) G.add_edge(x, rx, INF);
}
G.n = tot+1;
cout << G.Dinitz() << endl;
}

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK