hdu 4714 Tree2cycle

发布时间:2016-12-8 12:07:37 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4714 Tree2cycle",主要涉及到hdu 4714 Tree2cycle方面的内容,对于hdu 4714 Tree2cycle感兴趣的同学可以参考一下。

Tree2cycle Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others) Total Submission(s): 792    Accepted Submission(s): 182 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 Hint In the sample above, you can disconnect (2,4) and then connect (1, 4) and (3, 4), and the total cost is 3.     #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> using namespace std; const int MAXN = 1000000 + 50; struct Edge { int v, next; }edge[MAXN * 2]; bool vis[MAXN]; int head[MAXN], e, ans, n; void add(int u, int v) { edge[e].v = v; edge[e].next = head[u]; head[u] = e++; } void init() { e = 0; ans = 0; memset(head, -1, sizeof(head)); memset(vis, false, sizeof(vis)); } bool dfs(int x) { int sum = 0; vis[x] = true; for (int i = head[x]; i != -1; i = edge[i].next) { int v = edge[i].v; if (!vis[v]) { sum += dfs(v); } } if (sum >= 2) { ans += x == 1 ? 2 * (sum - 2) : 2 * (sum - 1); return false; } else { return true; } } void input() { int t, u, v; cin >> t; while (t--) { cin >> n; init(); for (int i = 0; i < n - 1; i++) { cin >> u >> v; add(u, v); add(v, u); } dfs(1); cout << ans + 1 << endl; } } int main() { std::ios::sync_with_stdio(false); input(); return 0; }  

上一篇:SilkTest FAQ 7
下一篇:OftenTap亲密度通讯录: 联系人亲密度管理, 群发短信/邮件, 快捷拨号器

相关文章

相关评论