大家好，又见面了，我是全栈君。
题目大意：
给出一棵树。求去掉一条边之后两棵子树节点权值和作差的最小值。
解题思路：
这不知道怎么用树形DP做，仅仅是个DFS就过了。还手残了一次。
思路详细看代码。
以下是代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;
int min(int a,int b)
{
if(a>b)a=b;
return a;
}
int max(int a,int b)
{
if(a<b)a=b;
return a;
}
struct node
{
int to,next;
} edge[100005*2];
int n,m,cnt,head[100005];
long long weight[100005],min1,sum;
const long long inf = 100000000000000ll;
bool vis[100005];
void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].to=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool chack(int src)
{
int t=head[src];
while(t!=-1)
{
if(!vis[edge[t].to])return true;
t=edge[t].next;
}
return false;
}
long long llaabs(long long num)
{
if(num<0)num=-num;
return num;
}
long long dfs(int src)
{
long long ans=weight[src],temp;
vis[src]=true;
if(chack(src))
{
int t=head[src];
while(t!=-1)
{
if(!vis[edge[t].to])
{
temp=dfs(edge[t].to);
min1=min(min1,llaabs(sum-temp-temp));
ans+=temp;
}
t=edge[t].next;
}
}
return ans;
}
int main()
{
int case1=1;
while(scanf("%d%d",&n,&m),n||m)
{
cnt=0;
int u,v;
min1=inf;
sum=0;
memset(vis,false,sizeof(vis));
memset(head,-1,sizeof(head));
for(int i=1; i<=n; i++)
{
scanf("%lld",&weight[i]);
sum+=weight[i];
}
for(int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
}
dfs(1);
printf("Case %d: %lld\n",case1++,min1);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116301.html原文链接：https://javaforall.net
