树的最大连通分支问题

树的最大连通分支问题

时间： 1ms        内存：128M

描述：

给定一棵树T，树中每个顶点u 都有一个权w(u)，权可以是负数。现在要找到树T 的一个连通子图使该子图的权之和最大。

输入：

输入的第1 行有1 个正整数n，表示树T 有n 个顶点。树T 的顶点编号为1，…，n。第2 行有n 个整数，表示n 个顶点的权值。接下来的n-1 行中，每行有表示树T 的一条边的2 个整数u,v，表示顶点u与顶点v相连。

输出：

将计算出的最大连通分支的权值输出。

示例输入：

5
-1 1 3 1 -1
4 1
1 3
1 2
4 5

示例输出：

4

提示：

参考答案（内存最优[1712]）：

#include<iostream>
#include <fstream>   
using namespace std;   
struct Cnode   
{   
    long weight;  
    int father;  
    int childnum; 
    long wMax; 
    bool visited; 
};   
int main()   
{
    int i;   
    long n,u,v;    
    cin>>n;   
    Cnode *tree=new Cnode[n+1];
    for (i=1;i<=n;i++)  
    {   
        tree[i].father=0;   
        tree[i].childnum=0;   
        tree[i].visited=false;   
        cin>>(tree[i].weight);   
        tree[i].wMax=tree[i].weight;   
    }          
    for (i=1;i<=(n-1);i++) 
    {   
        cin>>u>>v;   
        tree[v].father=u;   
        tree[u].childnum++;   
    }   
    int root;   
    for (i=1;i<=n;i++)  
        if (tree[i].father==0)   
            root=i;   
    while (tree[root].childnum>0) 
    {   
        for (i=1;i<=n;i++)   
            if ((tree[i].childnum==0)&&(!tree[i].visited))   
            {   
                tree[i].visited=1;   
                tree[tree[i].father].childnum--;   
                if (tree[i].wMax>0)   
                    tree[tree[i].father].wMax=tree[tree[i].father].wMax+tree[i].wMax;   
            }   
    }   
    long max=tree[1].wMax;
    for (i=2;i<=n;i++)
        if (tree[i].wMax>max)   
            max=tree[i].wMax;   
    cout<<max;
    delete [] tree;   
    return 0;   
}

参考答案（时间最优[0]）：

#include<iostream>
#include <fstream>   
using namespace std;   
struct Cnode   
{   
    long weight;  
    int father;  
    int childnum; 
    long wMax; 
    bool visited; 
};   
int main()   
{
    int i;   
    long n,u,v;    
    cin>>n;   
    Cnode *tree=new Cnode[n+1];
    for (i=1;i<=n;i++)  
    {   
        tree[i].father=0;   
        tree[i].childnum=0;   
        tree[i].visited=false;   
        cin>>(tree[i].weight);   
        tree[i].wMax=tree[i].weight;   
    }          
    for (i=1;i<=(n-1);i++) 
    {   
        cin>>u>>v;   
        tree[v].father=u;   
        tree[u].childnum++;   
    }   
    int root;   
    for (i=1;i<=n;i++)  
        if (tree[i].father==0)   
            root=i;   
    while (tree[root].childnum>0) 
    {   
        for (i=1;i<=n;i++)   
            if ((tree[i].childnum==0)&&(!tree[i].visited))   
            {   
                tree[i].visited=1;   
                tree[tree[i].father].childnum--;   
                if (tree[i].wMax>0)   
                    tree[tree[i].father].wMax=tree[tree[i].father].wMax+tree[i].wMax;   
            }   
    }   
    long max=tree[1].wMax;
    for (i=2;i<=n;i++)
        if (tree[i].wMax>max)   
            max=tree[i].wMax;   
    cout<<max;
    delete [] tree;   
    return 0;   
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。