P5934 [清华集训2012]最小生成树

简要题意

给你一个 \(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 <bits/stdc++.h>

#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<<2];

	int head[N],ec,dis[N],now[N];

	bool vis[N];

	void add(int u,int v,int w){

		g[++ec].nxt=head[u];

		g[ec].to=v;

		g[ec].w=w;

		head[u]=ec;

	}

	int bfs(){

		memset(dis,0x3f,sizeof(dis));

		memset(vis,0,sizeof(vis));

		queue<int> 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&&sum;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<Edge> graph;

signed main(){

	cin>>n>>m;

	for(int i=1,u,v,w;i<=m;i++){

		cin>>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<<ret+dinic()<<'\n';

	return 0;

}

巴特西

P5934 [清华集训2012]最小生成树

简要题意

思路

代码

最新文章

热门文章