[文章目录]
Description
给你一张无向图，n个点，m条边。询问一条边加入之后至少去掉多少条边能够使其可能在最小生成树上，也可能在最大生成树上。n<=20000,m<=200000
哈哈哈，dinic :O(跑得过)
假设这条边即存在在最大生成树上，又存在在最小生成树上，那么说明大于这条边的所有边不能够使该边的两端点联通，那么，考虑最少去掉多少边使得两点不连通，这就是裸的最小割问题了。最小生成树同理。
讲真一开始想偏了。
1.无脑直接扔边+并查集判断。发现不一定是最优解，有可能之前一条边的原因导致很多边都加不进去了。
2.prim思想（naive）：将两端点的所有出边不等于L的累计数量。发现prim算法可能求出的生成树连接端点的不一定就是一条边。所以不是最优解。
3.kruskal思想，一条边被加入当且仅当比他小的边不能讲两端点联通。最大生成树同理。然后就变成最小割问题了。
网络流果然是O(跑的过)啊，233
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans,s,t,L,a[201000],b[201000],w[201000];
int head[20010],to[401000],nxt[401000],f[401000],cnt=1;
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=1;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
f[cnt]=1;
}
int dis[20010];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",a+i,b+i,w+i);
scanf("%d%d%d",&s,&t,&L);
for(int i=1;i<=m;i++)
if(w[i]<L) add(a[i],b[i]);
while(bfs()) ans+=dinic(s,1<<30);
cnt=1; memset(head,0,sizeof head);
for(int i=1;i<=m;i++)
if(w[i]>L) add(a[i],b[i]);
while(bfs()) ans+=dinic(s,1<<30);
printf("%d\n",ans);
return 0;
}