poj 3585 Accumulation Degree（二次扫描和换根法）

Accumulation Degree

大致题意：有一棵流量树，它的每一条边都有一个正流量，树上所有度数为一的节点都是出口，相应的树上每一个节点都有一个权值，它表示从这个节点向其他出口可以输送的最大总流量。我们的任务就是求这个最大总流量。

$ solution: $

这一道题需要仔细思考其性质，我们发现如果我们把某一个节点当做是这棵树的根，并求出了这一个点的权值，那么与它相连的节点我们也可以求出来。这是二次扫描和换根法的前提条件。现在我们详细的分析一下这一题的性质：如果我们现在有两个节点 $ i $ 和 $ j $ ， $ j $ 是 $ i $ 的儿子， $ i $ 是根节点，然后我们用树形 $ DP $ 求出了 $ i $ 号结点的权值（这个过程里我们肯定会求得 $ j $ 流向 $ j $ 这可子树的流量），这样我们发现 $ j $ 的权值是可以通过 $ i $ $ O(1) $ 求出来的。因为我们已经求出了 $ j $ 流向 $ j $ 这棵子树的流量，然后只要我们求出 $ j $ 通过 $ i $ 流向其他子树的流量就可以得出 $ j $ 的权值，而这个就是用 $ i $ 的权值减去它流向 $ j $ 的流量，然后再和 $ e( i,j ) $ 这条边的流量取最小值即可。然后我们发现我们的 $ j $ 节点已经拥有了作为一个根节点的条件，所以 $ j $ 又可以当做一个新的根节点来更新其他的节点。

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

const ll inf=(ll)1e12;

ll ans;

int t,n,id,top;

ll a[200005];

ll f[200005];

int du[200005];

int tou[200005];

bool vis[200005];

struct su{

	int to,v,next;

}b[400005];

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;

	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();

	return sign?-res:res;

}

inline ll min(ll x,int y){

	if(x<y)return x;

	return y;

}

inline void add(int x,int y,int v){

	b[++top].to=y; b[top].v=v;

	b[top].next=tou[x]; tou[x]=top;

}

inline void dfs(int i){ vis[i]=1;

	if(du[i]<2){a[i]=inf;return;}

	for(rg j=tou[i];j;j=b[j].next){

		rg to=b[j].to; if(vis[to])continue;

		dfs(to); a[i]+=min(a[to],b[j].v);

	}

}

inline void upd(int i,int fa,int v){

	//cout<<i<<" "<<a[i]<<endl;

	a[i]+=min(a[fa]-v,v); ans=max(ans,a[i]);

	for(rg j=tou[i];j;j=b[j].next){

		rg to=b[j].to;

		if(to==fa||du[to]<2)continue;

		upd(to,i,b[j].v);

	}

}

int main(){

	//freopen("in.in","r",stdin);

	//freopen(".out","w",stdout);

	t=qr();

	while(t--){

		n=qr(); top=0; ans=0; id=0;

		if(n<2){puts("0");continue;}

		if(n<3){qr();qr();cout<<qr()<<endl;continue;}

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

			a[i]=f[i]=du[i]=tou[i]=vis[i]=0;

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

			rg x=qr(),y=qr(),v=qr();

			add(x,y,v); add(y,x,v);

			++du[x]; ++du[y];

			if(du[x]>du[id])id=x;

			if(du[y]>du[id])id=y;

			//cout<<x<<" "<<du[x]<<" "<<y<<" "<<du[y]<<" "<<id<<" "<<du[id]<<endl;

		}dfs(id); ans=a[id];

		//cout<<id<<endl;

		//cout<<"root:"<<id<<endl;

		for(rg i=tou[id];i;i=b[i].next)

			if(du[b[i].to]>1)upd(b[i].to,id,b[i].v);

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

poj 3585 Accumulation Degree（二次扫描和换根法）

Accumulation Degree

$ solution: $

$ code: $

最新文章

热门文章