题面

思路

考虑一个决策方案${x}$，$x_i$表示第$i$个点选不选，$f^k_i$表示点$i$的第$k$个父亲

那么可以得到总花费的表达式$ans=\sum V_i x_i - \sum max(x_i-min(x_{f^1_i},x_{f2_i},x_{f^3_i},...x_{fk_i}),0)\ast P_i$

优化一下表达方式：把收益和支出分开

$ans=\sum_{V_i>0} V_i - \sum_{V_i>0} V_i (1-x_i) - \sum_{V_i<0} (-V_i)x_i - \sum max(x_i-min(x_{f^1_i},x_{f2_i},x_{f^3_i},...x_{fk_i}),0)\ast P_i$

看着很长是不是？其实它很简洁：全部正收益，减掉没拿到的正收益，减掉拿了的负收益，减掉因为限制关系导致的负收益

我们发现后面三个$\sum$都是要和$x_i$相关的决策变量

观察【这里我也不知道怎么观察的，反正题解是这么观察的= =】可以知道，这三个地方都可以对应经典的最小割模型

【解释一下】经典最小割模型，就是指一对源点汇点，然后中间两列分开的节点集合{l}，{r}

所有$(S,l)$和$(r,T)$的边都有值，$lr$中间的边代表限制关系

大概是这样的一个最小流，可以解决双向限制并行（也就大概相当于一个&）的最优化问题

这道题里面，我们发现运用这个技巧以后，前两个$\sum$的东西都很好解决了：

对于$V_i>0$的点，建立边$(S,i,V_i)$和$(i,T,0)$

对于$V_i<0$的点，建立边$(S,i,0)$和$(i,T,-V_i)$

这样可以很好的解决前两个限制，但是对于第三个限制怎么办呢？

我们发现我们实际上需要一个节点来代替$min(x_{f^1_i},x_{f2_i},x_{f^3_i},...x_{fk_i})$这一坨东西的功能

思考，一个节点$y_i$，如果代替了上面那个东西，那么意味着它小于任何一个$x_{f^k_i}$

那么就有限制关系$y_i \leq x_{f^{k_i}$，我们可以对于这个限制建边$(y_i,x_{f}k_i},inf)$，使得不会出现$y_i\le x_{f^k_i}$的情况

【这段看起来可能有点复杂，但是实际上就是分步建立边、建立最小割的限制关系而已，一定要细细理解】

建图完成以后，我们发现这个复杂度好像不太够啊，暴力建边肯定炸了啊

没关系，我们用树剖+线段树辅助建边一下就好了

这东西的边数是$O(n\log ^2n)$级别的，可以接受【总理论复杂度？那是什么？网络流有这东西吗？】

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#include<queue>

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

int n,v[100010],k[100010],p[100010];

namespace g{

	int first[100010],cnte=-1;

	void init(){memset(first,-1,sizeof(first));cnte=-1;}

	struct edge{

		int to,next,w;

	}a[6000010];

	inline void add(int u,int v,int w){

		a[++cnte]=(edge){v,first[u],w};first[u]=cnte;

		a[++cnte]=(edge){u,first[v],0};first[v]=cnte;

	}

	queue<int>q;int dep[100010],cur[100010];

	bool bfs(int s,int t){

		int i,u,v;

		for(i=s;i<=t;i++) dep[i]=-1,cur[i]=first[i];

		q.push(s);dep[s]=0;

		while(!q.empty()){

			u=q.front();q.pop();

			for(i=first[u];~i;i=a[i].next){

				v=a[i].to;if(!a[i].w||~dep[v]) continue;

				dep[v]=dep[u]+1;q.push(v);

			}

		}

		return ~dep[t];

	}

	int dfs(int u,int t,int lim){

		if(u==t||!lim) return lim;

		int i,v,f,flow=0;

		for(i=cur[u];~i;i=a[i].next){

			v=a[i].to;cur[u]=i;

			if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(lim,a[i].w)))){

				a[i].w-=f;a[i^1].w+=f;

				flow+=f;lim-=f;

				if(!lim) return flow;

			}

		}

		return flow;

	}

	int dinic(int s,int t){

		int re=0;

		while(bfs(s,t)) re+=dfs(s,t,1e9);

		return re;

	}

}

int fa[1000010],dep[100010],siz[100010],son[100010],back[100010],dfn[100010],top[100010],clk;

namespace t{

	int first[100010],cnte=-1;

	void init(){memset(first,-1,sizeof(first));}

	struct edge{

		int to,next;

	}a[200010];

	inline void add(int u,int v){

		a[++cnte]=(edge){v,first[u]};first[u]=cnte;

		a[++cnte]=(edge){u,first[v]};first[v]=cnte;

	}

	void dfs1(int u,int f){

		int i,v;

		dep[u]=dep[f]+1;

		siz[u]=1;son[u]=0;

		for(i=first[u];~i;i=a[i].next){

			v=a[i].to;if(v==f) continue;

			dfs1(v,u);

			siz[u]+=siz[v];

			if(siz[son[u]]<siz[v]) son[u]=v;

		}

	}

	void dfs2(int u,int t){

		int i,v;

		top[u]=t;

		dfn[u]=++clk;back[clk]=u;

		if(son[u]) dfs2(son[u],t);

		for(i=first[u];~i;i=a[i].next){

			v=a[i].to;if(v==fa[u]||v==son[u]) continue;

			dfs2(v,v);

		}

	}

}

namespace seg{

	int seg[100010],cnt;

	void init(){cnt=n;}

	void build(int l,int r,int num){

		if(l==r){seg[num]=back[l];return;}

		int mid=(l+r)>>1;

		seg[num]=++cnt;

		build(l,mid,num<<1);g::add(seg[num],seg[num<<1],1e9);

		build(mid+1,r,num<<1|1);g::add(seg[num],seg[num<<1|1],1e9);

	}

	void add(int l,int r,int ql,int qr,int num,int from){

		assert(ql);

		if(l>=ql&&r<=qr){g::add(from,seg[num],1e9);return;}

		int mid=(l+r)>>1;

		if(mid>=ql) add(l,mid,ql,qr,num<<1,from);

		if(mid<qr) add(mid+1,r,ql,qr,num<<1|1,from);

	}

}

void link(int u,int tot){//树剖辅助建边

	if(!tot) return;

	int from=u+seg::cnt;

	u=fa[u];

	while(tot){

		if(tot>=dep[u]-dep[top[u]]+1){

			seg::add(1,n,dfn[top[u]],dfn[u],1,from);

			tot-=dep[u]-dep[top[u]]+1;

			u=fa[top[u]];

		}

		else{

			seg::add(1,n,dfn[u]-tot+1,dfn[u],1,from);

			break;

		}

	}

}

int main(){

	n=read();int i,S,T,ans=0;

	t::init();

	for(i=1;i<=n;i++){

		fa[i]=read();v[i]=read();k[i]=read();p[i]=read();

		if(fa[i]) t::add(fa[i],i);

	}

	t::dfs1(1,0);

	t::dfs2(1,1);

	g::init();

	seg::init();

	seg::build(1,n,1);

	S=0;T=seg::cnt+n+1;

	for(i=1;i<=n;i++){

		if(v[i]>=0){

			ans+=v[i];

			g::add(S,i,v[i]);

			g::add(i,T,0);

		}

		else{

			g::add(S,i,0);

			g::add(i,T,-v[i]);

		}

		g::add(i,i+seg::cnt,p[i]);

		link(i,k[i]);

	}

	printf("%d\n",ans-g::dinic(S,T));

}

巴特西

[xsy1129] flow [树链剖分和线段树一起优化网络流][我也不知道这是什么鬼标签]

题面

思路

Code

最新文章

热门文章