Minimum Cut
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5452Description
Given a simple unweighted graph G (an undirected graph containing no loops nor multiple edges) with n nodes and m edges. Let T be a spanning tree of G.
We say that a cut in G respects T if it cuts just one edges of T.Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph G respecting the given spanning tree T.
Input
The input contains several test cases.
The first line of the input is a single integer t (1≤t≤5) which is the number of test cases.Then t test cases follow.Each test case contains several lines.
The first line contains two integers n (2≤n≤20000) and m (n−1≤m≤200000).The following n−1 lines describe the spanning tree T and each of them contains two integers u and v corresponding to an edge.Next m−n+1 lines describe the undirected graph G and each of them contains two integers u and v corresponding to an edge which is not in the spanning tree T.Output
For each test case, you should output the minimum cut of graph G respecting the given spanning tree T.
Sample Input
Sample Output
HINT
题意
给你一个没有自环重边的无向图,然后给你一颗生成树,让你求一个最小割集的大小,使得这个割集有且只有一条边在这棵生成树上
题解:
树形dp,对于这个点,如果要消除他和他父亲之间的联系的话,代价就是他的子树所有连向外界的边就好了
跑一遍dfs维护一下就行了
-------------------------
我的方法是错的,已经被hack了
数据:
代码:
//qscqesze#include#include #include #include #include #include #include #include #include #include #include #include #include