hdu 4005 The war

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

(边)双连通分量 + 树dp

题意:给定一个连通的无向图,你只能毁掉一条边,而敌人可以补回一条边(但不会补你毁的那条,是任意地补另外一条)。为了保证你一定能使这个图断裂,你至少需要多少钱

步骤:

  1. 先对无向图求一次双连通 分量,求出所有的桥并且对原图缩点。可知缩点后是一棵无根树。可知如果在一个双连通分量内毁边是徒劳的,一定不能使图断裂,只有毁桥才能使图断裂,对应过来即毁掉树的树边。如果缩点后整个图就是一个点即一个双连通分量,那么这个图是不会断裂的,直接输出-1结束
  2. 得到一棵无根树后想想怎么解决这个问题。选出权值最小的一条边,以边的两个端点为树根确立两棵树。在这两棵树中进行树dp,两边做法一样,只解释一边。
  3. 确定了树根遍历下去后,要记录一些信息
    • fa[u],点u的父亲
    • val[u],点u指向其父亲的那条边(存在且唯一)的权值
    • dp[u],以点u为根的子树中最小的边权(不包括val[u]这条边因为这条已经是连向u的父亲不需要u子树内的边)
    • index[u],对应上面的dp数组,记录子树下是哪个点引出的边权值最小
  4. 在一棵子树里找出了权值最小的边以及它对应的点u,从u回到树根的路径是唯一的,把路径的边全部标记。继续在以u为根的子树下进行迭代,同样是找一个权值最小的以及它对应的点uu,从u回到树根u的路径是唯一的,把路径的边全部标记。直到找到叶子为止。
  5. 这样的选择策略,是从防守者的角度来考虑的,而不是从毁边的角度考虑。防守者要连上2个点,那么这2点间的路径都不能毁了因为形成了环,毁边的目的是使代价最小,而防守的目的是保护树不断裂,即使断裂也要让对方付出最大的代价。那么防守者一定要保护权值最小的边,让它在环上。如果权值最小的边不在环上,只要毁掉这个边就行了,代价又是最小的。所以无论如果要从权值最小的边开始保护,但是确定一条边后,有些边也随着确定了(该点回到树根的边),那么还剩下该点下的子树,同样的,也要保护权值最小的边…………………
  6. 此时可以考虑一下为什么最初要找出权值最小的边,然后确定两棵树然后做树dp,这个思想和上面的思想是相同的,也是防守者为了保护最小的边,一定要经过最小边。

注意:

  1. 数据中有无重边?没测试过的,但是tarjan写法中是能处理有重边或无重边的情况的
  2. 一开始图是否连通?是连通的,还要任意一个点出发做一次tarjan即可
  3. 网上的代码都是用另一种思想来写树dp的,其实意思和上面说的一样,不过速度比上面的代码快因为少了标记边和找答案这些步骤;那些代码一般跑出30,15ms,我的代码还能跑到60ms。
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 10010
#define M 100010
#define INF 0x3f3f3f3f
#define cl memset
#define pb push_back

struct edge{
int u,v,w,next;
bool used;
};
struct bri{
int u,v,w;
bri(int x,int y,int z){
u = x; v = y; w = z;
}
};
struct tree{
int v,w;
tree(int x,int y){
v = x; w = y;
}
};
int head[N];
edge e[2*M];
vector<bri>bridge;
vector<tree>t[N];
int n,tot;
int dfn[N],low[N],dcnt,bcnt,belong[N],stack[N],top;
int node,__node,minw;
int fa[N],dp[N],val[N],index[N],vis[N];
int ans;

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

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v , w = e[k].w;
if(e[k].used) continue;
e[k].used = e[k^1].used = true;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u]){
bridge.pb(bri(u,v,w));
}
}
else low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
belong[x] = bcnt;
if(x == u) break;
}
}
}
void bcc(){
dcnt = top = bcnt = 0;
bridge.clear();
cl(dfn,0,sizeof(dfn));
tarjan(1);
}

void rebuild(){ //根据双连通分量来建树
node = __node = 0; minw = INF;
for(int i = 0; i <= n; i++)
t[i].clear();
for(int i = 0; i < bridge.size(); i++){
int u = belong[bridge[i].u];
int v = belong[bridge[i].v];
int w = bridge[i].w;
t[u].pb(tree(v,w));
t[v].pb(tree(u,w));
if(w < minw){
node = u;
__node = v;
minw = w;
}
}
}


void dfs(int u,int par){ //树dp,记录信息
for(int i = 0; i < t[u].size(); i++){
int v = t[u][i].v , w = t[u][i].w;
if(v == par) continue;
fa[v] = u; val[v] = w;
dfs(v,u);
if(dp[v] < dp[u]){
dp[u] = dp[v];
index[u] = index[v];
}
if(w < dp[u]){
dp[u] = w;
index[u] = v;
}
}
}
void treedp(){
for(int i = 1; i <= n; i++){
fa[i] = -1; val[i] = 0; dp[i] = INF; index[i] = -1;
}
fa[node] = __node; fa[__node] = node;
val[node] = val[__node] = minw;
dfs(node,__node);
dfs(__node,node);
}

void path(int root){ //根据index的信息沿路径返回,标记边
int son;
son = index[root];
while(true){
if(son == -1) break;
int temp = son;
while(son != root){
vis[son] = 1;
son = fa[son];
}
root = temp;
son = index[root];
}
}
void solve(){
cl(vis,0,sizeof(vis));
vis[node] = vis[__node] = 1;
path(node);
path(__node);
ans = INF;
for(int i = 1; i <= bcnt; i++)
if(!vis[i] && val[i] < ans)
ans = val[i];
if(ans == INF) cout << -1 << endl;
else cout << ans << endl;
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
tot = 0;
cl(head,-1,sizeof(head));
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
bcc();
if(bridge.size() == 0){
puts("-1");
continue;
}
rebuild();
treedp();
solve();
//test();
}
return 0;
}

/*
void test(){
puts("连通分量");
for(int i = 1; i <= n; i++)
printf("%d[%d]\n",i,low[i]);
puts("所有的桥");
for(int i = 0; i < bridge.size(); i++)
printf("%d --- %d %d\n",bridge[i].u,bridge[i].v,bridge[i].w);
puts("最小权值的桥");
printf("%d --- %d %d\n",node,__node,minw);
puts("Fa");
for(int i = 1; i <= n; i++)
if(used[i])
printf("%d[%d]\n",i,fa[i]);
puts("Val");
for(int i = 1; i <= n; i++)
if(used[i])
printf("%d[%d]\n",i,val[i]);
puts("Dp");
for(int i = 1; i <= n; i++)
if(used[i])
printf("%d[%d]\n",i,dp[i]);
puts("Index");
for(int i = 1; i <= n; i++)
if(used[i])
printf("%d[%d]\n",i,index[i]);
puts("Vis");
for(int i = 1; i <= n; i++)
if(used[i] && vis[i])
printf("%d\n",i);
}
*/