hdu 4612 Warm up

本文从WordPress迁移而来, 查看全部WordPress迁移文章

边双连通分量 + 树dp求最长链

【2013多校联合训练第二场】

题意:给出一个无向图(有重边),只允许在图中添加一条边,使得图中消掉最多的桥,输出只剩下多少桥

  1. 无向图求求一次边双连通分量并保存下所有的桥
  2. 根据连通分量来缩点,无向图根据边双连通分量缩点后得到的是一棵无根树
  3. 树中每个节点就是一个边双连通分量,内部没有桥,不用添加边。而每一条树边就是原图中的一条桥。
  4. 在无根树中找一条最长链,最长链的两个端点对应为u,v,连接u,v,那么u->lca(u,v)->v这条最长链路径中的所有树边都将得到保护,不再是桥,这样就消掉了所有的桥
  5. 剩下不在u->lca(u,v)->v路径中的树边仍然是桥,剩下的条数是 树边数 - (最长链 - 1),最长链是用节点数定义的,1-2-3,最长链为3,边数为2

注意:本体数据很大,点数200000,边数1000000,递归会爆栈,开栈挂。最好方法是把tarjan求bcc写成非递归

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
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 200010
#define M 2000010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
bool used;
}e[M];
int tree[N];
struct treeedge{
int u,v,next;
}et[M];
int dcnt,bcnt,top,dfn[N],low[N],belong[N],stack[N];
bool ins[N];
int bridge[N][2],len;
int dp[N][2],maxlink;

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v; e[tot].used = false;
e[tot].next = head[u]; head[u] = tot++;
}

inline void __add(int u ,int v){
et[tot].u = u; et[tot].v = v;
et[tot].next = tree[u]; tree[u] = tot++;
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int k = head[u]; k != -1; k = e[k].next)
if(!e[k].used){
e[k].used = e[k^1].used = true;
int v =e[k].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v])
low[u] = min(low[u],dfn[v]);
if(dfn[u] < low[v]){
bridge[len][0] = u;
bridge[len++][1] = v;
}
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
ins[x] = false; belong[x] = bcnt;
if(x == u) break;
}
}
}

void bcc(){
dcnt = bcnt = top = len = 0;
cl(dfn,0); cl(ins,false);
tarjan(1);
}

void rebuild(){
cl(tree,-1); tot = 0;
for(int i = 0; i < len; i++){
int u = belong[bridge[i][0]];
int v = belong[bridge[i][1]];
__add(u,v); __add(v,u);
}
}

void dfs(int u,int fa){
dp[u][0] = dp[u][1] = 0;
for(int k = tree[u]; k != -1; k = et[k].next){
int v = et[k].v;
if(v == fa) continue;
dfs(v,u);
if(dp[v][0] > dp[u][0]){
dp[u][1] = dp[u][0]; dp[u][0] = dp[v][0];
}
else if(dp[v][0] > dp[u][1])
dp[u][1] = dp[v][0];
}
dp[u][0]++; dp[u][1]++;
maxlink = max(maxlink , dp[u][0]+dp[u][1]-1);
}

void treedp(){
maxlink = 0;
dfs(1,-1);
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
cl(head,-1); tot = 0;
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
bcc();
rebuild();
treedp();
printf("%d\n",len - (maxlink-1));
}
return 0;
}