正題

題目鏈接:https://www.luogu.com.cn/problem/P5934

---

題目大意

給出$n$個點$m$條邊的一張圖，再加入一條邊$(u,v,L)$求至少刪掉多少條邊可以使得這條邊即在最小生成樹上又在最大生成樹上。

$1\le n\le 2\times 10^4,1\le m\le 2\times 10^5$

---

解題思路

稍微思考一下就不難發現這兩個問其實是沒有影響的，因為第一個問顯然只需要刪去邊權小于$L$的，第二個問顯然只需要刪去邊權大于$L$的。所以考慮分開求然后相加

那么考慮怎么讓它在最小生成樹上。考慮我們之前$\text{LCT}$維護最小生成樹的做法，我們加入一條邊$(u,v,w)$的時候，是找到$u～v$路徑上的最大邊然后和$w$比較。

那么如果原圖中存在一條不經過這條邊的路徑且最大值比$u,v$要小。那么顯然這條路徑可以完全取代這條邊，所以這條邊一定不是最小生成樹上的邊。

那么同理我們只需要把所有邊權小于$L$的邊加入，然后再刪去最少的邊使得$u,v$不連通即可。這個用最小割解決就好了。

最大生成樹同理

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=2e4+10,M=2e5+10,inf=1e9; struct node{int to,next,w; }a[M<<1]; struct edge{int x,y,w; }e[M]; int n,m,s,t,L,tot=1,ls[N],dep[N],ans; queue<int> q; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=w;return; } bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){if(x==t)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return flow;}if(!rest)dep[x]=0;return rest; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);scanf("%d%d%d",&s,&t,&L);for(int i=1;i<=m;i++)if(e[i].w<L)addl(e[i].x,e[i].y,1);while(bfs())ans+=dinic(s,inf);memset(ls,0,sizeof(ls));tot=0;for(int i=1;i<=m;i++)if(e[i].w>L)addl(e[i].x,e[i].y,1);while(bfs())ans+=dinic(s,inf);printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的P5934-[清华集训2012]最小生成树【最小割】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。