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 | #include <bits/stdc++.h>
using namespace std;
int qread();
namespace Dinic{
const long long INF = 1e18;
const int SIZ = 1e5 + 3;
int n, m;
int H[SIZ], V[SIZ], N[SIZ], F[SIZ], t = 1;
int add(int u, int v, int f){
V[++ t] = v, N[t] = H[u], F[t] = f, H[u] = t;
V[++ t] = u, N[t] = H[v], F[t] = 0, H[v] = t;
n = max(n, u);
n = max(n, v);
return t - 1;
}
void clear(){
for(int i = 1;i <= n;++ i)
H[i] = 0;
n = m = 0, t = 1;
}
int D[SIZ];
bool bfs(int s, int t){
queue <int> Q;
for(int i = 1;i <= n;++ i)
D[i] = 0;
Q.push(s), D[s] = 1;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = H[u];i;i = N[i]){
const int &v = V[i];
const int &f = F[i];
if(f != 0 && !D[v]){
D[v] = D[u] + 1;
Q.push(v);
}
}
}
return D[t] != 0;
}
int C[SIZ];
long long dfs(int s, int t, int u, long long maxf){
if(u == t)
return maxf;
long long totf = 0;
for(int &i = C[u];i;i = N[i]){
const int &v = V[i];
const int &f = F[i];
if(D[v] == D[u] + 1){
long long resf = dfs(s, t, v, min(maxf, 1ll * f));
totf += resf;
maxf -= resf;
F[i ] -= resf;
F[i ^ 1] += resf;
if(maxf == 0)
return totf;
}
}
return totf;
}
long long dinic(int s, int t){
long long ans = 0;
while(bfs(s, t)){
memcpy(C, H, sizeof(H));
ans += dfs(s, t, s, INF);
}
return ans;
}
}
namespace GHTree{
const int MAXN = 500 + 5;
const int MAXM = 1500 + 5;
const int INF = 1e9;
int n, m, U[MAXM], V[MAXM], W[MAXM], A[MAXM], B[MAXM];
void add(int u, int v, int w){
++ m;
U[m] = u;
V[m] = v;
W[m] = w;
A[m] = Dinic :: add(u, v, w);
B[m] = Dinic :: add(v, u, w);
n = max(n, u);
n = max(n, v);
}
vector <pair<int, int> > E[MAXN];
void build(vector <int> N){
int s = N.front();
int t = N.back();
if(s == t) return;
for(int i = 1;i <= m;++ i){
int a = A[i]; Dinic :: F[a] = W[i], Dinic :: F[a ^ 1] = 0;
int b = B[i]; Dinic :: F[b] = W[i], Dinic :: F[b ^ 1] = 0;
}
int w = Dinic :: dinic(s, t);
E[s].push_back(make_pair(t, w));
E[t].push_back(make_pair(s, w));
vector <int> P;
vector <int> Q;
for(auto &u : N){
if(Dinic :: D[u] != 0)
P.push_back(u);
else
Q.push_back(u);
}
build(P), build(Q);
}
int D[MAXN];
int cut(int s, int t){
queue <int> Q; Q.push(s);
for(int i = 1;i <= n;++ i)
D[i] = -1;
D[s] = INF;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(auto &e : E[u]){
int v = e.first;
int w = e.second;
if(D[v] == -1){
D[v] = min(D[u], w);
Q.push(v);
}
}
}
return D[t];
}
}
|