MYF

HDU 5452 Minimum Cut

Posted on | In | | Visitors

题目链接

HDU 5452

题目类型：LCA

题目分析

题目大意

给出一个无向无权图，共n个顶点m条边，前n-1行可以形成一棵生成树，问在图中，仅包含生成树的一条边的最小割的值为多少

解析

学了LCA之后其实就没怎么再用过LCA，一开始一看最小割，拼命的想要怎样去建图跑网络流，后来发现建不出来Orz

对于一个图来讲，我们一开始有它的一个生成树，因为是生成树，所以图中每一个点都在树上，我们只要把剩下的m - n + 1条边想象成建完树之后加入的即可。如果最简单的考虑，只有一颗生成树，没有别的边，那答案必然为1，这很简单。

如果我们加了一条图中的边呢？假如我们假如的边为下图中的H-M，如果我们割H和M的LCA所形成的子树之外的边的话，也就是除了以C为根节点的树，H-M连线对他们是没有影响的，如果我们想割C-G这条边以分裂以G为顶点的子树的话，我们就必须割开M-H边。所以我们可以对图中的每一条不在树上的边u-v这样处理，cnt[u]++, cnt[v]++表示切当前点，或者以当前点为子树的点贡献的割的边数，如果要割的边在u和v所在的公共子树（即以两者LCA为根节点的子树）以外的地方的话，我们就把对应的LCA减去cnt2[lca]+=2;，因为u,v的两点贡献度都是树自身内部的，对于割当前边没有影响。

当处理剩下m-n+1条边的时候得到了cnt[]和cnt2[]，再自顶向下DFS一遍求出删每一条边所对应的割数即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=20000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int n , m , pre[maxn] ,rt[maxn], ecnt,cnt[maxn],cnt2[maxn],ans,cnt3[maxn];
bool vis[maxn];
struct edge
{
    int v , next;
} e[maxn *20];

int dep[maxn] , f[17][maxn] , Lev , s[maxn];///1<<16 < N, f[j][i] 表示i的第2^j个祖先

void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = pre[x] ; ~i ; i = e[i].next)
    {
        int y = e[i].v;
        if (y != fa)
        {
            dfs(y , x);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty())
    {
        int fa = q.front();
        q.pop();
        for (int i = pre[fa] ; ~i ; i = e[i].next)
        {
            int x = e[i].v;
            if (!vis[x])
            {
                dep[x] = dep[fa] + 1;
                f[0][x] = fa ,vis[x] = 1;
                q.push(x);
            }
        }
    }
}
int LCA(int x , int y)
{
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init()
{
    memset(pre , -1 , sizeof(pre));
    memset(cnt, 0, sizeof(cnt));
    memset(cnt2, 0, sizeof(cnt2));
    memset(rt,0,sizeof(rt));
    ecnt = 0;
}
void addedge(int x,int y)
{
    e[ecnt].v = y,
    e[ecnt].next = pre[x],
    pre[x] = ecnt ++;
}
int getLCA(int x,int y){
    if (dep[x] < dep[y])
        swap(x , y);
    return LCA(x , y);
}
void DFS2(int rt,int fa){
    cnt3[rt] = cnt[rt]+1;
    for (int i=pre[rt]; i!=-1; i=e[i].next) {
        int v = e[i].v;
        if (v!=fa) {
            DFS2(v, rt);
            cnt3[rt] += cnt3[v];
        }
    }
    cnt3[rt] -= cnt2[rt];
    ans = min(ans, cnt3[rt]);
}
void work()
{
    int i , j , x , y , z,anc;
    init();
    scanf("%d%d",&n,&m);
    for (i = 1 ; i < n ; ++ i)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
        rt[y]  =x;
    }
    for(int i=1; i<=n; i++)
    {
        if(rt[i]==0)
        {
            anc = i;    //确定树的根节点
            break;
        }
    }
    dfs(anc , 0);
    for (j = 1 ; 1 << j < n ; ++ j)
        for (i = 1 ; i <= n ; ++ i)
            f[j][i] = f[j - 1][f[j - 1][i]];
    Lev = j - 1;
    
    int u,v;
    for (int i=1; i<= m-n+1; i++) {
        scanf("%d%d",&u,&v);
        cnt[u]++;
        cnt[v]++;
        int lca = getLCA(u, v);
        cnt2[lca] += 2;
    }
    ans = INF;
    DFS2(anc, -1);
}

int main()
{
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        work();
        printf("Case #%d: %d\n",cas++,ans);
    }
    return 0;
}