poj 3140 树形去边差异最小-白红宇

poj 3140 树形去边差异最小

阅读量：5248 次

发布时间：2019-06-14

本文共 1703 字，大约阅读时间需要 5 分钟。

http://poj.org/problem?id=3140

依然是差异最小问题，不过这次是去边。思路是这样的，先记录每个点的子节点个数，然后遍历每个边。

有两个问题要注意:

abs可能会出编译适配问题，可以自己写一个

INF对LL是不够用的，所以加了个INFL

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define pf printf#define sf scanf#define spf sprintf#define pb push_back#define debug printf("!\n")#define MAXN 110000+5#define MAX(a,b) a>b?a:b#define blank pf("\n")#define LL long long#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define pqueue priority_queue#define Rabs(a) (a<0?-a:a)#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fint n,m;struct node{ int y,val,next;}tree[MAXN<<2];int head[MAXN],vis[MAXN],ptr=1,dp[MAXN];LL num[MAXN],sum,ans,a[MAXN];void init(){ mem(head,-1); mem(vis,0); mem(dp,0); ans =INFL; sum =0; ptr=1;}void add(int x,int y){ tree[ptr].y = y; tree[ptr].next = head[x]; head[x] = ptr++;}void dfs(int rt){ vis[rt]=1; num[rt] = a[rt]; for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); num[rt]+=num[y]; }}int main(){ int i,j,k,kase=1; while(~sf("%d%d",&n,&m) && n+m) { init(); for(i=1;i<=n;i++) { sf("%I64d",&a[i]); sum+=a[i]; } for(i=1;i<=m;i++) { int x,y; sf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); for(i=1;i<=n;i++) { for(j=head[i];j!=-1;j=tree[j].next) { int y = tree[j].y; LL tp = num[y]; ans = min(ans,Rabs((sum-2*tp))); //pf("t%d %d %d %d\n",i,ans,sum,2*num[y]); } } pf("Case %d: %I64d\n",kase++,ans); }}