Minimum Cut

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5452

Description

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

1 4 5 1 2 2 3 3 4 1 3 1 4

Sample Output

Case #1: 2

HINT

题意

给你一个没有自环重边的无向图，然后给你一颗生成树，让你求一个最小割集的大小，使得这个割集有且只有一条边在这棵生成树上

题解：

树形dp，对于这个点，如果要消除他和他父亲之间的联系的话，代价就是他的子树所有连向外界的边就好了

跑一遍dfs维护一下就行了

-------------------------

我的方法是错的，已经被hack了

数据：

4 4 1 2 2 3 3 4 1 3

4 4 1 3 2 3 2 4 1 2

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 20050#define mod 10007#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;//*********************************************************************************vector
                   
                     Q[maxn];vector
                    
                      E[maxn];int vis[maxn];int dp[maxn];int ans;void dfs(int x){ vis[x]=1; for(int i=0;i
                     
                      y)swap(x,y); Q[x].push_back(y); } for(int i=n-1;i
                      
                       y)swap(x,y); E[y].push_back(x); } dfs(1); printf("Case #%d: %d\n",cas,ans); }}

转载于:https://www.cnblogs.com/qscqesze/p/4822468.html

你可能感兴趣的文章