HDU 4714 Tree2cycle(树状DP)(2013 ACM/ICPC Asia Regional Online ―― Warmup)

Description

A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 unit of cost respectively. The nodes are labeled from 1 to N. Your job is to transform the tree to a cycle(without superfluous edges) using minimal cost. 
A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.
 

Input

The first line contains the number of test cases T( T<=10 ). Following lines are the scenarios of each test case.  In the first line of each test case, there is a single integer N( 3<=N<=1000000 ) - the number of nodes in the tree. The following N-1 lines describe the N-1 edges of the tree. Each line has a pair of integer U, V ( 1<=U,V<=N ), describing a bidirectional edge (U, V). 
 

Output

For each test case, please output one integer representing minimal cost to transform the tree to a cycle. 

题目大意:一棵有n个点的树,删边需要1的费用,增边需要1的费用,问最少需要多少费用才能得到一个环,不能用多余的边(即总共n条边)。

思路:首先我们可以这样考虑:我们先删掉x条边,那么之后再加上x+1条边,形成一个环。我们删掉x条边后,所有的点的度都不能大于2,那么就会出现多条链,再用x+1条边把这些链首尾相接就可以形成一个环。现在问题就转化成了给一棵树,问最少删掉多少条边,使得每个点的度不大于2。然后就是树状DP,用dp[i][0]表示,第i个点,连0个或1个子节点(度小于2)的最小费用。用dp[i][1]表示,第i个点,连0个或1个或2个子节点(度小于等于2)的最小费用。这样对每个点选择是不连或者连一个子节点,还是连两个子节点。然后随便搞,时间复杂度为O(n)。

PS:100W个点我看到好多人栈溢出了所以大家还是写非递归吧(实际上会不会溢出我不知道我没试过我一开始就写非递归)……我极少写非递归可能写得比较挫……

代码(2703MS):

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; const int MAXN = ;
const int MAXE = MAXN * ; int head[MAXN];
int stk[MAXN], stkp[MAXN], top;
int next[MAXE], to[MAXE];
int ecnt, n, T; void init() {
memset(head, , sizeof(head));
ecnt = ;
} void add_edge(int u, int v) {
to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++;
} int dp[MAXN][];
//0:连0 or 1个子节点,1:连两个子节点
int solve() {
top = ;
stk[top] = ; stkp[top] = head[];
while(top > ) {
int &p = stkp[top], u = stk[top];
if(to[p] == stk[top - ]) p = next[p];
if(p) {
int &v = to[p];
++top; stk[top] = v; stkp[top] = head[v];
p = next[p];
}
else {
int min1 = MAXN, min2 = MAXN;
dp[u][] = ;
for(int q = head[u]; q; q = next[q]) {
int &v = to[q];
if(v == stk[top - ]) continue;
++dp[u][];
dp[u][] += min(dp[v][], dp[v][]);
int x = dp[v][] - min(dp[v][], dp[v][]);
if(x < min1) {
min2 = min1;
min1 = x;
}
else min2 = min(min2, x);
}
int best = dp[u][];
dp[u][] = min(dp[u][], best - + min1);
dp[u][] = min(dp[u][], best - + min1 + min2);
--top;
}
}
return * min(dp[][], dp[][]) + ;
} int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
init();
int u, v;
for(int i = ; i < n; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v);
}
printf("%d\n", solve());
}
}
上一篇:厂商自定义USB设备类概述


下一篇:Html中鼠标悬停显示二级菜单的两种方法