考虑 kruskal 算法的过程。
先将边按边权排序，考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中，所以对于所有的边权小于 \(L\) 的边，我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x,y)\) 建立一条容量为 \(1\) 的边，最小割即为答案。
最大生成树的过程是类似的，加入所有边权大于 \(L\) 的边跑最小割，将两次网络流的答案加起来即可。
复杂度分析：
由于容量均为 \(1\)，所以在使用 Dinic 算法时间复杂度会降低，具体分析参考OI-wiki Dinic算法特殊情境下的复杂度分析反正能过就对了
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MX=1e6+7;
const ll INF=1e18+7;
struct Edge{
int from,to;
ll cap,flow;
int nxt;
}edge[MX];
struct e{
int u,v,c;
}cedge[MX];
bool cmp(e x,e y){return x.c<y.c;}
int head[MX],cur[MX],d[MX],tNode=0,cnt=0;
bool vis[MX];
int n,m,s,t,L;
void addE(int u,int v,ll c){
edge[tNode].from=u;
edge[tNode].to=v;
edge[tNode].cap=c;
edge[tNode].flow=0;
edge[tNode].nxt=head[u];
head[u]=tNode;
tNode++;
}
queue<int > q;
bool BFS() {
memset(vis,false,sizeof(vis));
d[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=head[p];i!=-1;i=edge[i].nxt){
int to=edge[i].to;
if(!vis[to]&&edge[i].flow<edge[i].cap){
d[to]=d[p]+1;
vis[to]=true;
q.push(to);
}
}
}
return vis[t];
}
ll DFS(int x,ll a){
//cout<<x<<endl;
if(x==t||a==0)return a;
ll flow=0,f;
for(int &i=cur[x];i!=-1;i=edge[i].nxt){
int to=edge[i].to;
if(d[x]+1==d[to]&&(f=DFS(to,min(a,edge[i].cap-edge[i].flow)))>0){
flow+=f;
a-=f;
edge[i].flow+=f;
edge[i^1].flow-=f;
if(a==0)break;
}
}
return flow;
}
ll DINIC(){
ll ret=0;
while(BFS()){
for(int i=1;i<=n;i++)cur[i]=head[i];
ret+=DFS(s,INF);
}
return ret;
}
void add(int x,int y,ll c){
addE(x,y,c);
addE(y,x,0);
}
ll solve(int l,int r){
for(int i=1;i<=n;i++)head[i]=-1;
tNode=0;
for(int i=l;i<=r;i++){
add(cedge[i].u,cedge[i].v,1);
add(cedge[i].v,cedge[i].u,1);
}
return DINIC();
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>cedge[i].u>>cedge[i].v>>cedge[i].c;
sort(cedge+1,cedge+1+m,cmp);
cin>>s>>t>>L;
int pos1=0,pos2=0;
for(int i=1;i<=m;i++){
if(cedge[i].c>=L&&pos1==0)pos1=i;
if(cedge[i].c>L&&pos2==0)pos2=i;
}
cout<<solve(1,pos1-1)+solve(pos2,m)<<endl;
return 0;
}