HDU 4714 Tree2cycle DP 2013杭电热身赛 1009

时间：2023-11-11 13:55:26

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4714

Tree2cycle

Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 400    Accepted Submission(s): 78

Problem 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.
Sample Input
1
4
1 2
2 3
2 4
Sample Output
3
题目大意：已知一棵树，切边与连边都需要1的cost。现在要把这棵树分割连接成为一个环，求最小cost。
解题思路：将整棵树拆成N个单枝(所有点的度小于2)，所需的cost即为2*N-1(拆成N个单枝需 N-1 cost，合成一个环需要 N cost)。
可用树形DP求出N最小的情况，用dp[i][j]表示以i为根的可用度为j的最小单枝数。
状态转移方程：dp[root][0]=min(dp[root][0]+dp[son][0],dp[root][1]+dp[son][1]-1)
　　　　　　　dp[root][1]=min(dp[root][1]+dp[son][0],dp[root][2]+dp[son][1]-1)
　　　　　　　dp[root][2]=dp[root][2]+dp[son][0]
P.S. 该题的数据量较大，要加#pragma comment(linker,"/STACK:1024000000,1024000000")语句，而且要用C++编译器，不能用G++。
 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #pragma comment(linker,"/STACK:1024000000,1024000000")

 using namespace std;

 #define N 1000005

 #define M 2000010

 int vis[N],all,first[N],next[M],v[M],e,degree[N],dp[N][];

 void addedge(int x,int y)

 {

     v[e]=y;

     next[e]=first[x];

     first[x]=e++;

 }

 void dfs(int root)

 {

     int i,k;

     dp[root][]=dp[root][]=dp[root][]=;

     vis[root]=;

     for(i=first[root];i!=-;i=next[i])

     {

         k=v[i];

         if(!vis[k])

         {

             dfs(k);

             dp[root][]=min(dp[root][]+dp[k][],dp[root][]+dp[k][]-);

             dp[root][]=min(dp[root][]+dp[k][],dp[root][]+dp[k][]-);

             dp[root][]=dp[root][]+dp[k][];

         }

     }

 }

 int main()

 {

     int t,i,x,y;

     scanf("%d",&t);

     while(t--)

     {

         memset(dp,,sizeof(dp));

         memset(first,-,sizeof(first));

         e=;

         all=;

         int n;

         scanf("%d",&n);

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

         {

             scanf("%d%d",&x,&y);

             addedge(x,y);

             addedge(y,x);

         }

         memset(vis,,sizeof(vis));

         dfs();

         all=min(dp[][],min(dp[][],dp[][]));

         // cout<<all<<endl;

         printf("%d\n",all*-);

     }

     return ;

 }

本人入ACM时间尚短，写的不好的地方请多见谅。

相关文章