【树形dp+前向星】Godfather POJ - 3107

分手后的思念是犯贱 2022-06-14 10:17 155阅读 0赞

Think:  
1题意：给出一棵树，询问试探删除一个结点后可使得余下两个连通子图中的最大结点子图的结点数量是所有结点试探的最小值（找到一个点,其所有的子树中最大的子树节点数最少）  
[树的重心——参考自百度百科][Link 1]  
２思路：  
1>结点可达到5000不能使用邻接矩阵存储，因此使用前向星存储边的关系  
2>DFS试探(+树形dp)寻找最优解  
[树形dp建议参考博客１][dp]  
[树形dp建议参考博客２][dp 1]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 50004;
    const int inf = 0x3f3f3f3f;
    
    struct Edge{
        /*int w;//边的权值*/
        int to;
        int next;
    }edge[N*2];/*前向星存储边的信息*/
    
    int cnt, n, head[N], num[N], vis[N], ago = inf;
    vector<int> ans;/*不定长数组*/
    
    void Init_head();/*前向星head数组初始化*/
    void add_edge(int u, int v);/*加边*/
    void DFS(int u);
    
    int main(){
        int i, u, v;
        while(scanf("%d", &n) != EOF){
            Init_head();
            cnt = 0;/*注意初始化*/
            for(i = 0; i < n-1; i++){
                scanf("%d %d", &u, &v);
                add_edge(u, v);
                add_edge(v, u);/*无向图双加边*/
            }
            memset(vis, 0, sizeof(vis));
            memset(num, 0, sizeof(num));
            DFS(1);
            sort(ans.begin(), ans.end());/*对不定长数组进行升序排序*/
            int l = ans.size();
            for(i = 0; i < l; i++){
                printf("%d%c", ans[i], i == l-1? '\n': ' ');
            }
        }
        return 0;
    }
    void Init_head(){
        for(int i = 0; i <= n; i++)
            head[i] = -1;
    }
    void add_edge(int u, int v){
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
    void DFS(int u){
        vis[u] = 1;/*标记当前结点已经计算*/
        num[u] = 1;
        int i, tmp = 0;
        for(i = head[u]; ~i; i = edge[i].next){
       /*前向星结点遍历*/
            int v = edge[i].to;
            if(!vis[v]){
                DFS(v);/*试探当前结点的子树*/
                num[u] += num[v];/*累加子树结点数量*/
                tmp = max(tmp, num[v]);/*更新试探*/
            }
        }
        tmp = max(tmp, n-num[u]);/*试探两个连通子图的最大值*/
        if(tmp < ago){
            ago = tmp;
            ans.clear();/*清空所有元素*/
            ans.push_back(u);/*向尾部插入元素*/
        }
        else if(tmp == ago){
            ans.push_back(u);/*向尾部插入元素*/
        }
    }

[Link 1]: http://baike.baidu.com/link?url=Fe5_SWaY2nL81Nz4pq6e5R8CqdXBQ-JiQ5RIwHTZ8eLblSpG2hTDPFNk5njV6LjDGZwYYqK74TNl8eZO2GmUPvlzAbkxIjdB2bowRlDfMd0LkqOXjb7hnXuiLeoaPL_W
[dp]: http://blog.csdn.net/txl199106/article/details/45372337
[dp 1]: http://blog.csdn.net/lmyclever/article/details/6667412
[vjudge]: https://vjudge.net/problem/POJ-3107