正题

题目链接:https://www.luogu.com.cn/problem/P4716

题目大意

给出\(n\)个点\(m\)条边的一张有向图，求以\(r\)为根的最小外向树。

\(1\leq n\leq 100,1\leq m\leq 10^4\)

解题思路

考虑一种贪心，对于每个点我们先选出一个连入的最小的边权，但是这样可能产生环。

考虑暴力将环去掉，我们枚举所有的环，然后将环缩成一个点，之后然后每个环外的边都减去入点所连接边的权值（可撤销贪心）。

然后问题规模就缩小了，不断重复上述过程即可。

时间复杂度\(O(n(n+m))\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=110;

struct node{

	int x,y,w;

}e[N*N];

int n,m,r,h[N],pre[N],v[N],id[N],ans;

int main()

{

	scanf("%d%d%d",&n,&m,&r);

	for(int i=1;i<=m;i++)

		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);

	while(1){

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

		memset(v,0,sizeof(v));

		memset(id,0,sizeof(id));

		for(int i=1;i<=m;i++)

			if(e[i].x!=e[i].y&&e[i].w<h[e[i].y])

				h[e[i].y]=e[i].w,pre[e[i].y]=e[i].x;

		for(int i=1;i<=n;i++)

			if(i!=r&&h[i]==h[0])return puts("-1")&0;

		int cnt=0;

		for(int p=1;p<=n;p++){

			if(p==r)continue;

			int x=p;ans+=h[x];

			while(x!=r&&v[x]!=p&&!id[x])v[x]=p,x=pre[x];

			if(x!=r&&!id[x]){

				id[x]=++cnt;

				for(int y=pre[x];y!=x;y=pre[y])id[y]=cnt;

			}

		}

		if(cnt==0)break;

		for(int i=1;i<=n;i++)

			if(!id[i])id[i]=++cnt;

		for(int i=1;i<=m;i++){

			e[i].w-=h[e[i].y];

			e[i].x=id[e[i].x];

			e[i].y=id[e[i].y];

		}

		r=id[r];n=cnt;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

P4716-[模板]最小树形图

正题

题目大意

解题思路

code

最新文章

热门文章