首页 > 代码库 > 【BZOJ2521】[Shoi2010]最小生成树 最小割

【BZOJ2521】[Shoi2010]最小生成树 最小割

2024-11-25 16:55:39   203人阅读

【BZOJ2521】[Shoi2010]最小生成树

Description

Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树：

当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 P1P2，再把图中除了这条边以外的边，每一条的权值都减少1。如图 4所示就是一次这样的操作：

Input

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。
接下来m行依次描述标号为1,2,3…m的无向边，每行描述一条边。每个描述包含3个整数x、y、d，表示这条边连接着标号为x、y的点，且这条边的权值为d。
输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行，这行只有一个整数，即，使得标号为Lab边一定出现最小生成树中的最少操作次数。

Sample Input

4 6 1
1 2 2
1 3 2
1 4 3
2 3 2
2 4 4
3 4 5

Sample Output

1

HINT

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D<10^6

题解：首先，除了一条边，所有边的权值-1等价于这条边的权值+1。然后我们回忆Kruskal的过程，这条边保证在最小生成树上，等价于：如果我们只加入权值<=这条边权值的边，该条边的两端点无法连通。那么直接转化成最小割问题，割掉每条边的代价=选定边权值-当前边权值+1即可。

#include <cstdio>#include <cstring>#include <iostream>#include <queue>using namespace std;int n,m,cnt,S,T,lab,ans;int pa[810],pb[810],pc[810],to[100000],next[100000],val[100000],head[510],d[510];queue<int> q;inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int dfs(int x,int mf){	if(x==T)	return mf;	int i,k,temp=mf;	for(i=head[x];i!=-1;i=next[i])	{		if(d[to[i]]==d[x]+1&&val[i])		{			k=dfs(to[i],min(temp,val[i]));			if(!k)	d[to[i]]=0;			val[i]-=k,val[i^1]+=k,temp-=k;			if(!temp)	break;		}	}	return mf-temp;}int bfs(){	memset(d,0,sizeof(d));	while(!q.empty())	q.pop();	int i,u;	q.push(S),d[S]=1;	while(!q.empty())	{		u=q.front(),q.pop();		for(i=head[u];i!=-1;i=next[i])		{			if(!d[to[i]]&&val[i])			{				d[to[i]]=d[u]+1;				if(to[i]==T)	return 1;				q.push(to[i]);			}		}	}	return 0;}void add(int a,int b,int c){	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;	to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;}int main(){	n=rd(),m=rd(),lab=rd();	int i;	for(i=1;i<=m;i++)	pa[i]=rd(),pb[i]=rd(),pc[i]=rd();	memset(head,-1,sizeof(head));	for(i=1;i<=m;i++)	if(i!=lab&&pc[i]<=pc[lab])	add(pa[i],pb[i],pc[lab]-pc[i]+1),add(pb[i],pa[i],pc[lab]-pc[i]+1);	S=pa[lab],T=pb[lab];	while(bfs())	ans+=dfs(S,1<<30);	printf("%d",ans);	return 0;}

【BZOJ2521】[Shoi2010]最小生成树 最小割


联系
我们