最大流【省选模拟赛】

5K代码的恶心数据结构题

Posted by yjjr's blog on March 6, 2018

标签:树链剖分,线段树

题目

这里写图片描述

N<=1e5,M,Q<=2e5

保证询问中S,T不相等

分析

最大流就是最小割

对于M=N-1的情况,显然只需要割掉两点间权值最小的边

对于全部数据,我们发现每次最小割割掉的边只出现在

  • 所有简单路径都包含的任何一条边

  • 不同在两者间任意简单路径,但在一个环内的两条边

将每个环断成链后,用线段树维护,再将环缩点,做树链剖分

对于一次询问(S,T),先求出LCA(S,T)

将其转化为两条路径,考虑一些特殊的情况

重链直接在树剖内查询,轻边在原本的线段树内查询

如果修改的是非环边,直接在树剖内单点修改

否则在一开始建出的线段树内修改,再修改这个环在树剖内对应节点的重儿子的权值


毒瘤题考码力,硬肝了5h才AC

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=1e5+6;
struct node{
	node *lc,*rc;int lower;
	void update(){lower=min(lc->lower,rc->lower);}
}pool[maxn<<2],*cur=pool;
struct SegTree{//线段树指针写法
	node *root;int n;
	void modify(node *u,int ul,int ur,int p,int k){
		if(ul==ur){u->lower=k;return;}
		int mid=(ul+ur)>>1;
		if(p<=mid)modify(u->lc,ul,mid,p,k);else modify(u->rc,mid+1,ur,p,k);
		u->update();
	}
	inline int query(node *u,int ul,int ur,int l,int r){
		if(l<=ul&&ur<=r)return u->lower;
		int mid=(ul+ur)>>1,re=inf;
		if(l<=mid)re=min(re,query(u->lc,ul,mid,l,r));
		if(r>mid)re=min(re,query(u->rc,mid+1,ur,l,r));
		return re;
	}
	void build(node *&u,int ul,int ur,int *val){
		u=cur++;
		if(ul==ur){u->lower=val[ul];return;}
		int mid=(ul+ur)>>1;
		build(u->lc,ul,mid,val);
		build(u->rc,mid+1,ur,val);
		u->update();
	}
	void modify(int p,int k){modify(root,1,n,p,k);}
	inline int query(int l,int r){return l>r?inf:query(root,1,n,l,r);}
	void init(int _n,int *val){n=_n;build(root,1,n,val);}
}segt;
struct edge{int to,next,w;}e[maxn<<2];
int n,m,cnt,last[maxn],belong[maxn],st[maxn],id[maxn],num[maxn];
bool vis[maxn];int sta[maxn],len,idx,ori[maxn];
inline void insert(int u,int v,int w){e[++cnt]=(edge){v,last[u],w};last[u]=cnt;}
inline int calc(int u,int v){
	if(u==v)return inf;
	int sec=belong[u];
	if(id[u]>id[v])swap(u,v);
	return segt.query(id[u],id[v]-1)+min(segt.query(id[v],st[sec]+num[sec]-1),segt.query(st[sec],id[u]-1));
}
namespace tree{
	SegTree segt_tree;
	struct edge{int to,next,w,escape;}e[maxn<<1];
	int n,cnt,idx,last[maxn],num[maxn],val[maxn],ori[maxn];
	int dep[maxn],fa[maxn],top[maxn],pre[maxn],chain[maxn],dfn[maxn],heavy[maxn],pos[maxn];
	inline void insert(int u,int v,int w,int o){e[++cnt]=(edge){v,last[u],w,o};last[u]=cnt;}
	void dfs1(int u){
		num[u]=1;
		reg(u){
			int &v=belong[e[i].to];
			if(fa[u]==v)continue;
			fa[v]=u,dep[v]=dep[u]+1;
			top[v]=e[i].to,pre[v]=e[i].escape,val[v]=e[i].w;
			dfs1(v);
			num[u]+=num[v];
		}
	}
	void dfs2(int u,int Fa){
		pos[dfn[u]=++idx]=u,chain[u]=Fa;
		reg(u){
		    int &v=belong[e[i].to];
		    if(v==fa[u])continue;
		    if(num[v]>num[heavy[u]])heavy[u]=v;
		}
		if(!heavy[u])return;
		dfs2(heavy[u],Fa);
		reg(u){
		    int &v=belong[e[i].to];
		    if(v==fa[u]||v==heavy[u])continue;
		    dfs2(v,v);
		}
	}
	void init(){
		dfs1(1);dfs2(1,1);
		rep(i,1,n)
			if(heavy[fa[i]]==i&&fa[i]!=1)ori[dfn[i]]=min(val[i],calc(pre[i],top[fa[i]]));
		segt_tree.init(n,ori);
	}
	inline int getlca(int u,int v){
		while(chain[u]!=chain[v]){
			if(dep[chain[u]]>dep[chain[v]])swap(u,v);
			v=fa[chain[v]];
		}
		if(dep[u]>dep[v])swap(u,v);
		return u;
	}
	inline int getanc(int u,int Fa){
		int now=0;
		while(chain[u]!=chain[Fa])now=u,u=fa[chain[u]];
		return u==Fa?chain[now]:pos[dfn[Fa]+1];
	}
	inline int chain_query(int u,int Fa){
		int re=val[Fa];
		while(chain[u]!=chain[Fa]){
			re=min(min(re,calc(pre[chain[u]],top[fa[chain[u]]])),min(segt_tree.query(dfn[chain[u]]+1,dfn[u]),val[chain[u]]));
			u=fa[chain[u]];
		}
		re=min(re,segt_tree.query(dfn[Fa]+1,dfn[u]));
		return re;
	}
	inline int query(int u,int v){
		int Fa=getlca(belong[u],belong[v]);
		int u1=getanc(belong[u],Fa),v1=getanc(belong[v],Fa);
		int re=calc((u1?pre[u1]:u),(v1?pre[v1]:v));
		if(u1){
			re=min(re,calc(u,top[belong[u]]));
			re=min(re,chain_query(belong[u],u1));
		}
		if(v1){
			re=min(re,calc(v,top[belong[v]]));
			re=min(re,chain_query(belong[v],v1));
		}
		return re;
	}
	void modify(int u,int v,int w){
		if(belong[u]==belong[v]){
			int sec=belong[u];
			if((id[u]+1-st[sec])%(::num[sec])!=(id[v]-st[sec]))swap(u,v);
			segt.modify(id[u],w);
			int &tmp=heavy[sec];
			if(tmp&&fa[tmp]!=1)segt_tree.modify(dfn[tmp],min(val[tmp],calc(pre[tmp],top[fa[tmp]])));
		}else{
			u=belong[u],v=belong[v];
			if(dep[u]>dep[v])swap(u,v);
			val[v]=w;
			if(heavy[u]==v&&u!=1)segt_tree.modify(dfn[v],min(val[v],calc(pre[v],top[fa[v]])));
		}
	}
}//树剖板子
void getcir(int u,int Fa){
	vis[u]=true,sta[len++]=u;
	reg(u){
		int &v=e[i].to;
		if(v==Fa)continue;
		if(!vis[v]){
			getcir(v,u);
			if(belong[u]==belong[v])ori[id[v]]=e[i].w;
		}else if(!belong[v]){
			tree::n++;
			while(1){
				int tmp=sta[len-num[tree::n]-1];
				belong[tmp]=tree::n,id[tmp]=++idx;
				num[tree::n]++;
				if(tmp==v)break;
			}
			ori[id[v]]=e[i].w;st[tree::n]=id[u];
		}
	}
	if(!belong[u]){
		st[++tree::n]=id[u]=++idx;
		num[belong[u]=tree::n]=1;
	}
	len--;
}
void init(){
	n=read();int m=read();
	rep(i,1,m){
		int u=read(),v=read(),w=read();
		insert(u,v,w);insert(v,u,w);
	}
	getcir(1,0);segt.init(n,ori);
	rep(u,1,n)
		reg(u){
			int &v=e[i].to;
			if(belong[u]!=belong[v])tree::insert(belong[u],v,e[i].w,u);
		}
	tree::init();
}
void solve(){
	int T=read();
	while(T--){
		int opt=read(),u=read(),v=read();
		if(opt)tree::modify(e[u*2-1].to,e[u*2].to,v);else printf("%d\n",tree::query(u,v));
	}
}
int main()
{
	init();
	solve();
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr