一、问题描述(题目链接)
给你一棵树,删除或添加一条边的费用都是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 ;
}