例题：poj1848

参考来源：http://blog.csdn.net/sdjzping/article/details/18617173

题目：Tree

Time Limit: 1000MS Memory Limit: 30000K

Description

Consider a tree with N vertices, numbered from 1 to N. Add, if it is possible, a minimum number of edges thus every vertex belongs to exactly one cycle.

Input

The input has the following structure: N x(1) y(1) x(2) y(2) ... x(N-1) y(n-1) N (3 <= N <=100) is the number of vertices. x(i) and y(i) (x(i), y(i) are integers, 1 <= x(i), y(i) <= N) represent the two vertices connected by the i-th edge.

Output

The output will contain the value -1 if the problem doesn't have a solution, otherwise an integer, representing the number of added edges.

Sample Input

7 1 2 1 3 3 5 3 4 5 6 5 7

Sample Output

2

思路

首先明确一点，题中的环至少需要3个顶点。因此，对于树中的每个顶点，有3种状态。

f[x][0] 表示以x为根的树，变成每个顶点恰好在一个环中的图，需要连的最少边数。

f[x][1] 表示以x为根的树，除了根x以外，其余顶点变成每个顶点恰好在一个环中的图，需要连的最少边数。

f[x][2] 表示以x为根的树，除了根x以及和根相连的一条链（算上根一共至少2个顶点）以外，其余顶点变成每个顶点恰好在一个环中的图，需要连的最少边数。

有四种状态转移（假设正在考虑的顶点是R，有k个儿子）

A.根R的所有子树自己解决（取状态0），转移到R的状态1。即R所有的儿子都变成每个顶点恰好在一个环中的图，R自己不变。

B.根R的k-1个棵树自己解决，剩下一棵子树取状态1和状态2的最小值，转移到R的状态2。剩下的那棵子树和根R就构成了长度至少为2的一条链。

C.根R的k-2棵子树自己解决，剩下两棵子树取状态1和状态2的最小值，在这两棵子树之间连一条边，转移到R的状态0。

D.根R的k-1棵子树自己解决，剩下一棵子树取状态2（子树里还剩下长度至少为2的一条链），在这棵子树和根之间连一条边，构成一个环，转移到R的状态0。

代码

/* 
 本题有三种状态，分别是 
 dp[u][0],以u为根，所有的点都在环内 
 dp[u][1],以u为根，除了u外其余的都在环内 
 dp[u][2],以u为根，除了u和与u点相连的链（至少有两个点）外，其余的点都在环内 
 有四种状态转移 
 1、所有子节点都满足在环内，只有根节点不在环内， 
 dp[u][1]=min(INF,sum);(sum是所有的dp[v][0]的和) 
 2、有一个子节点不在环内，以该子节点有一条链，将此链连到以u为根的树上,(+1)就可以使得u的所有子节点都在环内 
 dp[u][0]=min(dp[u][0],sum-dp[v][0]+dp[v][2]+1); 
 3、有一个子节点不在环内，其余自己处理， 
 dp[u][2]=min(dp[u][2],sum-dp[v][0]+min(dp[v][1],dp[v][2])); 
 4、有两个不在环内，将这两个加一条边连起来就可使得所有都在环内 
 dp[u][0]=min(dp[u][0],sum-dp[v][0]-dp[k][0]+min(dp[v][1],dp[v][2])+min(dp[k][1],dp[k][2])+1); 
 */

#include<stdio.h>  
#include<vector>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
#define N 105  
#define INF 10000  
vector<int> adj[N*2];  
int vis[N];  
int dp[N][3];  
void dfs(int u)  
{  
    vis[u]=1;  
    vector<int> ch;  
    int sum=0,v;  
    for(int i=0; i<adj[u].size(); i++)  
    {  
        v=adj[u][i];  
        if(vis[v]==0)  
        {  
            dfs(v);  
            ch.push_back(v);  
            sum+=dp[v][0];  
        }  
    }  
    if(ch.size()==0)  
    {  
        dp[u][1]=0;  
        dp[u][0]=dp[u][2]=INF;  
        return;  
    }  
    dp[u][1]=min(INF,sum);  
    dp[u][2]=dp[u][0]=INF;  
    for(int i=0; i<ch.size(); i++)  
    {  
        v=ch[i];  
        dp[u][2]=min(dp[u][2],sum-dp[v][0]+min(dp[v][1],dp[v][2]));  
        dp[u][0]=min(dp[u][0],sum-dp[v][0]+dp[v][2]+1);  
    }  
    for(int i=0; i<ch.size(); i++)  
    {  
        v=ch[i];  
        for(int j=0; j<ch.size(); j++)  
        {  
            if(i==j)  
                continue;  
            int k=ch[j];  
            dp[u][0]=min(dp[u][0],sum-dp[v][0]-dp[k][0]+min(dp[v][1],dp[v][2])+min(dp[k][1],dp[k][2])+1);  
        }  
    }  
}  
int main()  
{  
    int n,a,b;  
    scanf("%d",&n);  
    for(int i=1; i<n; i++)  
    {  
        scanf("%d%d",&a,&b);  
        adj[a].push_back(b);  
        adj[b].push_back(a);  
    }  
    memset(vis,0,sizeof(vis));  
    dfs(1);  
    if(dp[1][0]>=INF)  
        printf("-1\n");  
    else  
        printf("%d\n",dp[1][0]);  
    return 0;  
}