程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3140（經典-樹的dp）

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

上一頁:CodeForces 414 C. Mashmokh and Reverse Operation
下一頁:LeetCode | Two Sum

C++入門知識

C語言結構體裡的成員數組和指針(1)

單看這文章的標題，你可能會覺得好像沒什麼意思。你先別下這個

學習使用Google Test

配置好VS後, 編寫第一個Demo. &

數據結構學習之二叉樹(實踐篇)

hdu 3263 Ancient vending machine

題目：給定一個多邊形A，問能否穿過多邊形的洞B。分析

Levenshein distance最小編輯距離算法實現

Levenshein distance最小編輯距離算法實現

NYOJ：題目490 翻譯，nyoj題目490翻譯

NYOJ：題目490 翻譯，nyoj題目490翻譯題目鏈接：