树的最大连通分支问题

树的最大连通分支问题

时间: 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;   
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注