胡闹 tree

题目大意

给你一棵$n\le10^5$的树,你分别有白链、黑链$B,W\le30000$条。

你要把树上的点染成黑白。如果一条白链锁包含的点都被染成了白色,那你会的得到这条白链的奖励,黑链同理。

求最大奖励。

解析

我们首先假设所有的链都能选上并且不冲突。

那么我们只要最小化消去冲突的代价就可以了。

是不是很像最小割?

我们把一条链上所包含的点全部连起来构成一个网络流上的“大点”,然后就是分别处理黑链、白链之间连边,跑最小割就可以了。

但是这样每个点之间都可能会连一条$inf$的边(表示在都在一条链上,即最小割隔不断它),这样边数可能会爆炸。

怎么办呢?考虑优化连边。

一种可行的方法是上线段树

一个简单的方法是倍增,把一个大区间倍增成几个小区间,然后小区间之间连$inf$边来成为大区间,而不是一个点一个点地连。

这样边数就会显著减少,随便搞一搞就行了。

优化

时限$10s$卡常?怎么优化?

  • 优化$lca$:利用$dfn$,只用一次倍增就可以求出$lca$。这个用处不大,因为还有更好的方法求lca
  • 优化$Dinic$
    • 当前弧优化
    • 分层的时候从$T$开始分到$S$,我也不知道为什么这样会快很多。

Code

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
203
204
205
206
207
208
209
210
211
212
213
//modify std
//still learning

#define REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, inf = 1<<30;

namespace dinic
{
const int maxn = 4e6 + 10, maxm = 3e7 + 100;
int bg[maxn], ne[maxm], to[maxm], w[maxm], e = 1;
int S, T, dis[maxn], q[maxn], head, tail;
int cur[maxn];
void add(int x, int y, int z)
{
e++;
to[e] = y;
ne[e] = bg[x];
bg[x] = e;
w[e] = z;
}
void link(int a, int b, int c) {add(a, b, c);add(b, a, 0);}
bool bfs()
{
REP(i, S, T) dis[i] = -1;
dis[q[head = tail = 1] = T] = 0;
while (head <= tail)
{
int x = q[head++];
for (int i = bg[x]; i ;i = ne[i])
if (w[i ^ 1] && dis[to[i]] == -1) dis[q[++tail] = to[i]] = dis[x] + 1;
}
return dis[S] != -1;
}
int dfs(int x, int y = inf)
{
if (x == T || !y) return y;
int res = 0;
for (int &i = cur[x]; i ; i = ne[i])
if (w[i] && dis[to[i]] == dis[x] - 1)
{
int temp = dfs(to[i], min(y, w[i]));
if (temp > 0)
{
res += temp;
y -= temp;
w[i] -= temp;
w[i ^ 1] += temp;
if (!y) break;
}
}
return res;
}
void output()
{
REP(x, S, T)
for (int i = bg[x];i;i=ne[i])printf("%d %d %d\n",x,to[i],w[i]);
}
int work()
{
int ans = 0;
while (bfs())
{
REP(i, S, T) cur[i] = bg[i];
ans += dfs(S);
}
return ans;
}
}

int n, B, W, ans, LOG;
int dfn[maxn], dfs_clock, grand[maxn][20], depth[maxn];
namespace tree
{
int bg[maxn], ne[maxn << 1], to[maxn << 1], e;
void add(int x, int y)
{
e++;
to[e] = y;
ne[e] = bg[x];
bg[x] = e;
}
void dfs(int x)
{
dfn[x] = ++dfs_clock;
REP(i, 1, LOG) grand[x][i] = grand[grand[x][i-1]][i-1];
for (int i = bg[x]; i ; i = ne[i])
if (to[i] ^ grand[x][0])
{
grand[to[i]][0] = x;
depth[to[i]] = depth[x] + 1;
dfs(to[i]);
}
}
void init()
{
LOG = log2(n);
depth[1] = 1;
dfs(1);
}
int lca(int x, int y)
{
if (x == y) return x;
if (dfn[x] > dfn[y]) swap(x, y);
DREP(i, LOG, 0)
if (dfn[grand[y][i]] > dfn[x]) y = grand[y][i];
return grand[y][0];
}
}
using tree::add;
using tree::lca;
using dinic::link;
int L[maxn][20], R[maxn][20];
vector <pair <int, int> > E;
int cur;
void getl(int k, int t)
{
if (!L[k][t])
{
L[k][t] = ++cur;
getl(k, t - 1);
getl(grand[k][t-1], t-1);
link(L[k][t], L[k][t-1], inf);
link(L[k][t], L[grand[k][t-1]][t-1], inf);
}
}
int jump(int k, int d)
{
REP(i, 0, LOG)
if (d & (1 << i)) k = grand[k][i];
return k;
}
void getr(int k, int t)
{
if (!R[k][t])
{
R[k][t] = ++cur;
getr(k, t - 1);
getr(grand[k][t-1], t-1);
link(R[k][t-1], R[k][t], inf);
link(R[grand[k][t-1]][t-1], R[k][t], inf);
}
}
void linkl(int k,int a,int c)
{
if (a==c) return;
int t;
for (t=0;(1<<(t+1))<depth[a]-depth[c];t++);
getl(a, t);
link(k, L[a][t], inf);
a = jump(a, depth[a]-depth[c]-(1<<t));
getl(a, t);
link(k, L[a][t], inf);
}
void linkr(int k,int a,int c)
{
if (a==c) return;
int t;
for (t=0;(1<<(t+1))<depth[a]-depth[c];t++);
getr(a, t);
link(R[a][t], k, inf);
a = jump(a, depth[a]-depth[c]-(1<<t));
getr(a, t);
link(R[a][t], k, inf);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
cin >> n >> B >> W;ans = n;
REP(i, 2, n)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
}
tree::init();
REP(i, 1, n)
{
L[i][0] = R[i][0] = ++cur;
link(0, cur, 1);
}
while (B--)
{
int x, y, z, v;
scanf("%d%d%d", &x, &y, &v);z = lca(x, y);
++cur; ans += v;
link(0, cur, v);
linkl(cur, x, grand[z][0]);
linkl(cur, y, z);
}
while (W--)
{
int x, y, z, v;
scanf("%d%d%d", &x, &y, &v);z = lca(x, y);
++cur; ans += v;
E.push_back(make_pair(cur, v));
linkr(cur, x, grand[z][0]);
linkr(cur, y, z);
}
dinic::T = ++cur;
int siz = (int)E.size() - 1;
REP(i, 0, siz) link(E[i].first, cur, E[i].second);
REP(i, 1, n) link(i, cur, 1);
cout << ans - dinic::work() << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×