hdu 5452 HDU 5452 Minimum Cut 2015沈陽網絡賽（在線LCA）－IT工程師數位筆記本

文章出處

Minimum CutTime 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≤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 graphG respecting the given spanning tree T. Sample Input

1 4 5 1 2 2 3 3 4 1 3 1 4Sample 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。即問你圖的最小割集是多大？
題解：因為考慮生成樹中的每一個結點，將其子樹與其父節點分離需要去掉其父邊以及其子樹中的結點與其他子樹相連的邊，其父邊就是生成樹中的邊，與其他子樹相連的邊為非生成樹中的邊。這樣只需統計每一個子樹關聯的非生成樹中的邊數，取最小值，然后+1就是答案。
對于每一個結點i，設num[ i ]為結點 i 的子樹關聯的非生成樹中的邊數，或者說，num存的是刪除某個結點 i 需要刪除的邊的數量。則num[ i ] = sum( num [ k ] ) k為i的子節點。對于非生成樹中的邊的兩個結點u,v，不難發現，除了LCA(u,v)，u到LCA(u,v)以及v到LCA(u,v)所經過的所有節點的num[ i ]都增加了1，因此當處理每一條非生成樹中的邊的兩個頂點u,v，num[ u ] ++,num[ v ] ++，num[LCA(u,v)] - = 2，然后DFS，回溯時自底向上更新一邊num[ i ]的值即可。
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=='-') 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-1bool vis[26];struct edge{    int from, to;    int next;} e[2*N];int tot,head[N];int cnt;int num[N];void init(){    memset(head,-1,sizeof(head));    memset(vis,false,sizeof(vis));    memset(num,0,sizeof(num));    cnt = 0;}void addedge(int u, int v){    e[cnt].from = u;    e[cnt].to = v;    e[cnt].next = head[u];    head[u] = cnt++;}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;    for(int k=head[u]; k!=-1; k=e[k].next)        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);            addedge(u, v);            addedge(v, u);        }        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;}/*16 71 22 33 44 55 66 71 34 6輸出應該是：1 。。。 */=n;>=n;>,int>