# HDU 5452 Minimum Cut 2015沈阳网络赛（在线LCA）

2016-09-16

Minimum Cut Time Limit: 3000 2000 MS (Java Others)Memory Limit: 65535 102400 K (Java Others) Total Submission(s): 1514Accepted Submission(s): 715 Problem Description Given a simp

# Minimum Cut

Time Limit: 3000/2000 MS (Java/Others)Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 1514Accepted Submission(s): 715

Problem Description Given a simple unweighted graphG (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 graphG 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&le;t&le;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&le;n&le;20000) and m(n?1&le;m&le;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 graphG respecting the given spanning tree T. Sample Input

1 4 5 1 2 2 3 3 4 1 3 1 4
Sample Output

Case #1: 2

Source 2015 ACM/ICPC Asia Regional Shenyang Online
Recommend wange2014|We have carefully selected several similar problems for you:58715870586858675866 题意：给你一个图G，让你求删除最少多少的边可以使的图G变为不连通，且所删除的边有且仅有一条属于图G的生成树T。即问你图的最小割集是多大？

AC代码：
#pragma comment(linker, "/STACK:102400000,102400000")
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
typedef vector vi;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;
const ll mod = (1LL<<32);
const int N =8e4+7;
const int M=100010;
const int maxn=1001;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)
#define pi acos(-1.0)
#define in freopen("in.txt","r",stdin)
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
const int lowbit(int x) { return x&-x; }
//const int lowbit(int x) { return ((x)&((x)^((x)-1))); }
int read(){ int v = 0, f = 1;char c =getchar();
while( c < 48 || 57 < c ){if(c==&#39;-&#39;) f = -1;c = getchar();}
while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
return v*f;}
int dp[2*N][26];  //数组开到2*N，因为遍历后序列长度为2*n-1
bool vis[26];
struct edge
{
int from, to;
int next;
} e[2*N];
int cnt;
int num[N];
void init()
{
memset(vis,false,sizeof(vis));
memset(num,0,sizeof(num));
cnt = 0;
}
{
e[cnt].from = u;
e[cnt].to = v;
}
int ver[2*N], R[2*N], first[N];
//ver:节点编号  R：深度   first：点编号位置
void dfs(int u ,int dep)
{
vis[u] = true;
ver[++tot] = u;
first[u] = tot;
R[tot] = dep;
if( !vis[e[k].to] )
{
int v = e[k].to;
dfs(v, dep+1);
ver[++tot] = u;
R[tot] = dep;
}
}
void ST(int n)
{
for(int i=1; i<=n; i++)
dp[i][0] = i;
for(int j=1; (1< y) swap(x,y);
int res = RMQ(x,y);
return ver[res];
}

int DFS(int u,int fa)
{
for(int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if(v == fa)
continue;
DFS(v, u);
num[u]+=num[v];
}
return 0;
}

int main()
{
int t;
int cas = 0;
int n, m;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
int u, v;
for(int i = 0; i < n-1; i++)
{
scanf("%d%d",&u,&v);
}
for(int i = n; i <= m; i++)
{
scanf("%d%d",&u,&v);
int tt = LCA(u, v);
num[u]++;
num[v]++;
num[tt]-=2;//一条边两个端点 贡献为2
}
DFS(1, 1);
int ans = INF;
for(int i = 2; i <= n; i++)
{
ans = min(ans, num[i]+1);
}
printf("Case #%d: %d\n",++cas,ans);
}
return 0;
}
/*
1
6 7
1 2
2 3
3 4
4 5
5 6
6 7
1 3
4 6

*/