题目
给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
输入格式
第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。
输出格式
输出一行一个整数表示最少需要删掉的边的数量。
输入样例
3 2
3 2 1
1 2 3
1 2 2
输出样例
1
提示
对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；
对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。
题解
跪了QAQ怎么想得到是网络流，如此之大的范围
我们首先思考一下想要该边加入最小生成树，那么要使得加入这条边时u，v不连通
想想最小生成树的kruskal算法，在长度L之前如果存在一条路径使得u，v联通，那么轮到L时必定无法加入最小生成树
所以我们单独抽出所有权值<L的边，删减若干边使得u，v不连通
这就用到了最小割
最大生成树类似
可以证明，时间复杂度是(O(M^{1.5}))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 20005,maxm = 1000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int n,m;
struct EDGE{int to,nxt,f;};
struct node{int a,b,w;}e[maxm];
struct FLOW{
EDGE ed[maxm];
int h[maxn],ne,S,T,vis[maxn],d[maxn],cur[maxn];
void init(){memset(h,0,sizeof(h)); ne = 2;}
void build(int u,int v,int w){
ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;
ed[ne] = (EDGE){u,h[v],0}; h[v] = ne++;
}
bool bfs(){
for (int i = 1; i <= n; i++) d[i] = INF,vis[i] = false;
queue<int> q;
q.push(S); d[S] = 0; vis[S] = true;
int u;
while (!q.empty()){
u = q.front(); q.pop();
Redge(u) if (ed[k].f && !vis[to = ed[k].to]){
d[to] = d[u] + 1; vis[to] = true;
q.push(to);
}
}
return vis[T];
}
int dfs(int u,int minf){
if (u == T || !minf) return minf;
int f,flow = 0,to;
if (cur[u] == -1) cur[u] = h[u];
for (int& k = cur[u]; k; k = ed[k].nxt)
if (d[to = ed[k].to] == d[u] + 1 && (f = dfs(to,min(minf,ed[k].f)))){
ed[k].f -= f; ed[k ^ 1].f += f;
flow += f; minf -= f;
if (!minf) break;
}
return flow;
}
int maxflow(){
int flow = 0;
while (bfs()){
memset(cur,-1,sizeof(cur));
flow += dfs(S,INF);
}
return flow;
}
}G;
int main(){
n = read(); m = read();
for (int i = 1; i <= m; i++)
e[i].a = read(),e[i].b = read(),e[i].w = read();
G.init();
G.S = read(); G.T = read();
int ans = 0,L = read();
for (int i = 1; i <= m; i++)
if (e[i].w < L){
G.build(e[i].a,e[i].b,1);
G.build(e[i].b,e[i].a,1);
}
ans += G.maxflow();
G.init();
for (int i = 1; i <= m; i++)
if (e[i].w > L){
G.build(e[i].a,e[i].b,1);
G.build(e[i].b,e[i].a,1);
}
ans += G.maxflow();
printf("%d
",ans);
return 0;
}