简要题意
给你一个 (N) 个点，(M) 条边的 无向连通 带权图。给定一条边 ((u,v,L))，请问需要在原图中删除多少条边，使得将 ((u,v,L)) 插入图后，它既可能在最小生成树上，又可能在最大生成树上。
对于 (100\%) 的数据，满足 (N\leq 20000,M\leq 200000,L\leq 20000)。
如果一条插入边 ((u,v,L)) 后该边可能在最小生成树上，那么如果将边权小于 (L) 的边组成一个新图，则新图不连通。
证明：
- 如果新图连通，则对新图求最小生成树，则最小生成树一定是原图的最小生成树（显然），然后((u,v,L)) 就一定不在任意一个最小生成树中。与前句矛盾，所以必须不连通。
- 如果新图不连通，则不存在最小生成树，使得任意一条树边边权小于(L)。又因为原图连通，所以插入((u,v,L)) 后，原图依旧连通。如果原图的最小生成树边集为(S)，则满足(\forall (x,y,z) \in S,z \geq L)。((u,v,L)) 插入(S)，则最小生成树变为基环树。将环上最大边权的边删除，则该边一定不是((u,v,L))（除非环上边权都相等），所以((u,v,L)) 可能在插入后的最小生成树上。
（可能有一些不严谨，敬请指正）
同理可得：如果一条插入边 ((u,v,L)) 后该边可能在最大生成树上，那么如果将边权大于 (L) 的边组成一个新图，则新图不连通。
所以如果我们建出了这两个新图，则相当于就是在求删除多少条边后全图（其实就是 (u\to v)）不连通。最小割解决。
最后答案就是两图最小割答案和，由于两个图的割集的交集一定为空集（因为它们没有相同的点），所以可以加法原理。
最后说一句，为什么是题面可能是最小（最大）生成树呢，因为可能有边权相等的边。
时间复杂度 (O(\operatorname{maxflow}(n,m)))，可以通过本题。
#include
#define int long long
using namespace std;
int n,m;
const int N = 200000+5,M = 200000+5;
int s,t,U,V,L,ret;
namespace MaxFlow{
// 自己打一遍 Dinic 最大流，以防忘记
struct edge{
int nxt,to,w;
} g[M< q;
q.push(s);
dis[s]=0;
now[s]=head[s];
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(g[i].w>0 && !vis[v]){
q.push(v);
vis[v]=1;
now[v]=head[v];
dis[v]=dis[u]+1;
if(v==t){
return 1;
}
}
}
}
return 0;
}
int dfs(int x,int sum){
if(x==t){
return sum;
}
int k,res=sum;
for(int i=now[x];i&∑i=g[i].nxt){
now[x]=i;
int v=g[i].to;
if(g[i].w>0&&(dis[v]==dis[x]+1)){
k=dfs(v,min(res,g[i].w));
g[i].w-=k;
g[i^1].w+=k;
res-=k;
}
}
return sum-res;
}
int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,LLONG_MAX);
}
return ans;
}
void addedge(int u,int v,int cap){
add(u,v,cap);
add(v,u,-cap);
}
void clean(void){
ec=0;
memset(head,0,sizeof(head));
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(g,0,sizeof(g));
}
}
using namespace MaxFlow;
struct Edge{int from,to,weight;};
vector graph;
signed main(){
cin>>n>>m;
for(int i=1,u,v,w;i>u>>v>>w;
graph.push_back({u,v,w});
}
cin>>U>>V>>L;
s=U,t=V;
clean();
for(Edge i:graph){
if(i.weight < L){
addedge(i.from,i.to,1);addedge(i.to,i.from,1);
}
}
ret=dinic();
clean();
for(Edge i:graph){
if(i.weight > L){
addedge(i.from,i.to,1);addedge(i.to,i.from,1);
}
}
cout<
Original: https://www.cnblogs.com/zheyuanxie/p/p5934.html
Author: xiezheyuan
Title: P5934 [清华集训2012]最小生成树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604595/
转载文章受原作者版权保护。转载请注明原作者出处！