题解【CF786E ALT】

传送门。

$\texttt{Description}$

$n$ 个点的树，$m$ 个人。第 $i$ 个人的散步路径是从 $x_i$ 到 $y_i$。

一个人高兴当且仅当它获得了一个宠物或 $x_i$ 到 $y_i$ 每一条边上都有一个宠物。

问最少分发多少个宠物才能使所有居民高兴。

输出方案。

$1\le n\le 10^4$，$1\le m\le 2\times 10^4$。

$\texttt{Solution}$

思路三分钟，代码三小时。纪念一下 $\texttt{700 AC}$。

前置知识：网络流，线段树优化建图，树链剖分。

考虑一个显然的二分图。

所有人在左边，树上的边在右边。

对于一个人来说，要么给人宠物，要么给路径上所有边宠物。肯定不会同时给，这样就不满足最优了。

这就是很模板的最小割的模型了。

建图方式：

  • $s$ 向每一个人连一条流量为 $1$ 的边。
  • 每一个人向路径上的每一条边连流量为 $\infty$ 的边。
  • 最后树上每一条边向 $t$ 连流量 $1$ 的边。

稍微解释一下，$\infty$ 表示只能选一个，因为最小割不可能割掉 $\infty$ 的边。流量为 $1$ 是因为分发了一个宠物。

这样建图边数是 $nm$ 的。很容易想到线段树优化建图。

但是这是在树上，没关系，我们通过树链剖分，将一条路径分成若干个连续的区间，然后再用线段树优化建图就可以了。

问题在于输出方案。

先考虑第一行。

如果 $s$ 到某一个人的流量是 $0$，是不是说明，这个人被选取了，毕竟流量为 $0$ 了。

然后考虑树上某条边 $e$ 连到 $t$ 的一条边，有一条残余网络通向了 $e$，这么说明 $e$ 到 $t$ 的流量肯定为 $0$ 了，因为如果不是 $0$ 就又形成了一条增广路。

所以我们进行一遍 $\texttt{dfs}$ 来找到选取了哪些边。

但是注意，我们找到的所谓的“边”，只是在线段数中的节点编号，我们还需要一个数组映射出某个叶子节点编号对应维护的点，然后对应维护的点在映射出原树中的点，最后对于原树中国每一个点再维护它属于哪一个人（这个可以用 $\texttt{map}$ 来维护）。

代码巨难写：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rint() read()
#define rll() read()
using namespace std;
typedef long long ll;
inline int read()
{
	register int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template
inline T Min(T x,T y){return x
inline T Max(T x,T y){return x>y?x:y;}
template
inline void Swap(T&x,T&y){int t=x;x=y;y=t;return;}
const int MAXN(1e6+10);
const int MAXM(1e6+10);
int n,m;
int tyt[MAXN];
struct E{int to,nxt,flow;};
E edge[MAXM];
int head[MAXN],tot(1);
int s,t;
int pos[MAXN];
int que1[MAXN],t1,que2[MAXN],t2;
inline void add(int u,int v,int f)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].flow=f;
	return;
}
inline void add_edge(int u,int v,int f)
{
	add(u,v,f);
	add(v,u,0);
	return;
}
typedef pairP;
mapmp;
int par[MAXN],siz[MAXN],dep[MAXN],son[MAXN],top[MAXN],idx[MAXN],rk[MAXN],cnt;
int res[MAXN];
inline void dfs1(int u,int fa)
{
	par[u]=fa,siz[u]=1,dep[u]=dep[fa]+1;
	res[u]=mp[make_pair(u,fa)];
	for(register int i=head[u];i;i=edge[i].nxt)
	{
		E e=edge[i];
		if(e.to==fa) continue;
		dfs1(e.to,u);
		siz[u]+=siz[e.to];
		if(siz[e.to]>siz[son[u]]) son[u]=e.to;
	}
	return;
}
inline void dfs2(int u,int topf)
{
	top[u]=topf;
	idx[u]=++cnt;
	rk[cnt]=u;
	if(son[u]) dfs2(son[u],topf);
	for(register int i=head[u];i;i=edge[i].nxt)
	{
		E e=edge[i];
		if(e.to!=par[u]&&e.to!=son[u])	
			dfs2(e.to,e.to);
	}
	return;
}
struct Segment_Tree
{
	inline int lc(int p){return p<<1;}
	inline int rc(int p){return p<<1|1;}
	inline void push_down(int u,int ls,int rs)
	{
		add_edge(u,ls,INF);
		add_edge(u,rs,INF);
		return;
	}
	inline void build(int u,int l,int r)
	{
		if(l==r)
		{
			pos[u]=l;
			add_edge(u,t,1);
			return;
		}
		int mid=(l+r)>>1;
		build(lc(u),l,mid);
		build(rc(u),mid+1,r);
		push_down(u,lc(u),rc(u));
		return;
	}
	inline void update(int u,int l,int r,int ln,int rn,int k)
	{
		if(ln<=l&&r<=rn)
		{
			add_edge(k,u,INF);
			return;
		}
		int mid=(l+r)>>1;
		if(ln<=mid) update(lc(u),l,mid,ln,rn,k);
		if(rn>mid) update(rc(u),mid+1,r,ln,rn,k);
		return;
	}
};
Segment_Tree shit;
inline void ass(int k,int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx^fy)
	{
		if(dep[fx]dep[y]) Swap(x,y);
		shit.update(1,1,n,idx[x]+1,idx[y],k);
	}
	return;
}
queueq;
inline bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=edge[i].nxt)
		{
			E e=edge[i];
			if(e.flow&&!dep[e.to])
			{
				dep[e.to]=dep[u]+1;
				q.push(e.to);
			}
		}
	}
	return dep[t];
}
inline int dfs(int u,int in)
{
	if(u==t) return in;
	int out(0);
	for(register int i=head[u];i&∈i=edge[i].nxt)
	{
		E e=edge[i];
		if(e.flow&&dep[e.to]==dep[u]+1)
		{
			int now=dfs(e.to,Min(e.flow,in));
			edge[i].flow-=now;
			edge[i^1].flow+=now;
			in-=now;
			out+=now;
		}
	}
	if(!out) dep[u]=0;
	return out;
}
inline void remake()
{
	tot=1;
	memset(edge,0,sizeof(edge));
	memset(head,0,sizeof(head));
	return;
}
inline int num(int i){return i+n*4;}
inline int dinic()
{
	int ans(0);
	while(bfs()) ans+=dfs(s,INF);
	return ans;
}
bool vis[MAXN];
inline void find_way(int u)
{
	vis[u]=true;
	for(register int i=head[u];i;i=edge[i].nxt)
	{
		E e=edge[i];
		if(!vis[e.to]&&e.flow) find_way(e.to);
	}
	return;
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i


$$\texttt{The End.by UF}$$
网络流线段树优化建图树链剖分

相关

图论---网络流

网络流 学习笔记

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

Codeforces 1373F - Network Coverage（模拟网络流）

线段树学习笔记 1

关于 线段树 的一些认识

网络流24题-骑士共存

【网络流24题】最长不下降子序列问题

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

标签