首页 > 代码库 > poj3140（树的dfs）
poj3140（树的dfs）
题目链接：http://poj.org/problem?id=3140
题意：给定一棵n棵节点的树，求删去某条边后两个分支的最小差异值。
分析：num[u]表示以u点为根节点的子树的总人数，那么不在该子树的人数和为sum-num[u].dfs遍历一遍即可。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int head[N],tot,n,m;LL ans,sum,num[N];LL Abs(LL a){ return a>0?a:-a;}void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); num[u]+=num[v]; } ans=min(ans,Abs(sum-2*num[u]));}int main(){ int u,v,cas=1; while(scanf("%d%d",&n,&m)>0) { if(n==0&&m==0)break; tot=0; memset(head,-1,sizeof(head)); sum=0; for(int i=1;i<=n;i++) scanf("%lld",&num[i]),sum+=num[i]; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } ans=1LL<<50; dfs(1,-1); printf("Case %d: %lld\n",cas++,ans); }}
poj3140（树的dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。