本文共 1699 字，大约阅读时间需要 5 分钟。

一条权值为$val$的边(端点是$A$和$B$)在最小生成树中当且仅当权值小于$val$的边都连上后

这条边的两个端点还没有被连通。

这个很好理解,通过观察$krustal$算法可以知道使用并查集维护的连通性相当于把边都连上的连通性

再观察一下我们的操作,选择一条边不改变,使得其他边权值都减一

这其实等价于只把选中的边的权值加一,因为在构造最小生成树的过程中,只有边权的相对大小是有用的

那么一条边权值为$x$的边执行$max(0,val+1-x)$次操作后就无法影响到权值为$val$的边

所以在原图中连边,边的流量为$max(0,val+1-x)$,从$A$向$B$跑最大流/最小割即可解决问题

#include 
   
    using namespace std;const int maxn=5e6+10;const int inf=1e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){
   	d[++cnt]=(edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt]=(edge){
   u,head[v],0},head[v]=cnt;}int l[maxn],r[maxn],w[maxn],dis[maxn],n,m,lab,s,t,ans;bool bfs(int s,int  t){
   	queue
    
     q;	for(int i=0;i<=n;i++)	dis[i]=0;	dis[s]=1;  q.push( s );	while( !q.empty() )	{
   		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( dis[v]==0&&d[i].flow )			{
   				dis[v]=dis[u]+1;	q.push(v);				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int flow){
   	if( u==t )	return flow;	int res=flow;	for(int i=head[u]; i&&res ;i=d[i].nxt )	{
   		int v=d[i].to;		if( d[i].flow&&dis[v]==dis[u]+1 )		{
   			int temp=dinic(v,min(res,d[i].flow) );			if( temp==0 )	dis[v]=0;			d[i].flow-=temp; d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}int main(){
   	cin >> n >> m >> lab;	for(int i=1;i<=m;i++)	cin >> l[i] >> r[i] >> w[i];	for(int i=1;i<=m;i++)		if( i!=lab&&w[i]<=w[lab] )	add( l[i],r[i],w[lab]+1-w[i] ),add( r[i],l[i],w[lab]+1-w[i] );	s = l[lab], t = r[lab];	while( bfs( s,t ) )	ans += dinic( s,inf );	cout << ans;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115371090 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！