「BZOJ2561」最小生成树

Description

给定一个边带正权的连通无向图G=(V,E)G=(V,E),其中N=VN=|V|M=EM=|E|NN个点从11NN依次编号,给定三个正整数ssss,和LL (uv)(u\neq v),假设现在加入一条边权为LL的边(s,t)(s,t),那么需要删掉最少多少条边,才能够使得这条边既可能出现在最小生成树上,也可能出现在最大生成树上?

Input

第一行包含用空格隔开的两个整数,分别为NNMM
接下来MM行,每行包含三个正整数uuvvww表示图GG存在一条边权为ww的边(u,v)(u,v)
最后一行包含用空格隔开的三个整数,分别为sstt,和 LL
数据保证图中没有自环。

Output

输出一行一个整数表示最少需要删掉的边的数量。

Sample Input

1
2
3
4
3 2
3 2 1
1 2 3
1 2 2

Sample Output

1
1

HINT

对于2020%的数据满足N10,M20,L20N \leq 10,M \leq 20,L \leq 20
对于5050%的数据满足N300,M3000,L200N \leq 300,M \leq 3000,L \leq 200
对于100100%的数据满足N20000,M200000,L20000N \leq 20000,M \leq 200000,L \leq 20000

Solution

以最小生成树为例:
按照边权把边按照ww从小到大排序,对所有边的权值<<题目要求的LL都建立一条边,构成图G1G_1
(s,t)(s,t)这条边是没有用的,当图G1G_1sstt是联通的。为了让sstt不连通,即边(s,t)(s,t)是最小生成树中,那么就是求G1G_1sts\to t的最大割。
最大生成树同理。
两遍最大流答案相加即可。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 21000, M = 400000;
struct Edge {
int u, v, nxt, f;
}e[M * 2], a[M * 2];
int head[N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en ,e[en].f = 0;
}
int d[N], s, t, n,m;
bool bfs() {
for(int i = 1; i<= n; ++i) d[i] = 0;
d[s] = 1;
queue<int>q;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x];i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
k = dinic(e[i].v, min(e[i].f, rest));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
bool cmp(Edge _x, Edge _y) {
return _x.f < _y.f;
}
const int inf = 1e9;
int main() {
freopen("2561.in","r",stdin);
freopen("2561.out","w",stdout);
n = read(), m = read();
for(int i = 1; i<= m; ++i) {
a[i].u = read();
a[i].v = read();
a[i].f = read();
}
sort(a +1 ,a +1 + m, cmp);
int p = 1;
int w;
s = read(), t = read(), w = read();
if(s > t) swap(s, t);
while(p <= m && a[p].f < w) {
addedge(a[p].u, a[p].v, 1);
addedge(a[p].v, a[p].u, 1);
++p;
}
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
en = 1;
memset(head,0,sizeof head);
while(p <= m && a[p].f == w) ++p;
while(p <= m) {
addedge(a[p].u, a[p].v, 1);
addedge(a[p].v, a[p].u, 1);
++p;
}
while(bfs()) while(y = dinic(s, inf)) res += y;
writeln(res);
return 0;
}