poj3140（经典-树的dp） - c++编程基础

题意：一棵树，每个节点都有一个正的权值，将树剪断一条边，分成两棵树并使得两棵树的权值和之差的绝对值最小。求最小之差。

解法：记忆化dfs一遍，即枚举剪断每条边的情况，复杂度是O(n).

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               using namespace std; #define eps 1e-8 typedef long long LL; struct edge { int v; int next; } edges[200100]; int count1=0; int head[100100]; void addedge(int u,int v) { edges[count1].v=v; edges[count1].next=head[u]; head[u]=count1++; } bool vis[100100]; LL num[100100]; LL ans[100100]; LL out=0; int m,n; LL sum=0; LL fabs(LL x) { if(x>=0) return x; return -x; } bool dfs(int k) { if(vis[k]) return false; ans[k]+=num[k]; vis[k]=1; for(int i=head[k];i!=-1;i=edges[i].next) { int t=edges[i].v; if(dfs(t)) ans[k]+=ans[t]; } out=min(out,fabs(sum-2*ans[k])); return true; } int main() { //freopen ("in.txt" , "r" , stdin); int t=0; while(scanf("%d%d",&n,&m)==2) { if(m==0&&n==0)break; t++; sum=0; memset(vis,0,sizeof vis); memset(head,-1,sizeof head); memset(ans,0,sizeof ans); count1=0; for(int i=1;i<=n;i++) scanf("%lld",num+i),sum+=num[i]; out=sum; for(int i=0;i