树形dp——Tree2cycle

一、问题描述（题目链接）

给你一棵树，删除或添加一条边的费用都是1，问使它变成一个环的最小费用。

二、解题思路

回溯法，然后回溯的时候的当前节点度数>2(如果是成环的话肯定就是2或者小于2)就把它和父节点之间的边砍掉。每砍掉一次，以后是要连上的，只需乘2就行。由于是回溯回来的，父节点在子节点阶段就考虑了一次，相当于与该子节点与父节点没有边了，所以父节点的度数减1。

三、代码实现

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxn =  + ;

 vector<int>G[maxn];

 int degree[maxn],ans,n;

 void init()

 {

     ans = ;

     memset(degree, , sizeof(degree));

     for (int i = ; i <= n; i++)

         G[i].clear();

 }

 void dfs(int son, int fa)

 {

     int k = G[son].size();

     for (int i = ; i < k; i++)

     {

         int newson = G[son][i];

         if (newson == fa)    continue;

         dfs(newson, son);

         if (degree[newson] > )

         {

             degree[son]--;                //父节点要减一

             ans += (degree[newson] - ) * ;

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while (T--)

     {

         int a, b;

         init();

         scanf("%d", &n);

         for (int i = ; i < n; i++)

         {

             scanf("%d%d", &a, &b);

             degree[a]++;

             degree[b]++;

             G[a].push_back(b);

             G[b].push_back(a);

         }

         int root = ;

         for (int i = ; i <= n; i++)    //找到度数为一的节点作为根节点，开始搜索

         {

             if (degree[i] == )

             {

                 root = i;

                 break;

             }

         }

         dfs(root, );

         printf("%d\n", ans + );

     }

     return ;

 }

巴特西

树形dp——Tree2cycle

最新文章

热门文章