大家好,又见面了,我是全栈君。
题目大意:
给出一棵树。求去掉一条边之后两棵子树节点权值和作差的最小值。
解题思路:
这不知道怎么用树形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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116301.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...