bzoj 3559: [Ctsc2014]图的分割【最小生成树+并查集】

读题两小时系列……

在读懂题意之后，发现M(c)就是c这块最大权割边也就是的最小生成树的最大权边的权值，所以整个问题都可以在MST的过程中解决（M和c都是跟着并查集变的）

不过不是真的最小生成树，是合并了所有a[i].w<=min(b[zhao(f[a[i].u])]+z[c[zhao(f[a[i].u])]],b[zhao(f[a[i].v])]+z[c[zhao(f[a[i].v])]])的边的若干联通块，根据定义那样的边不能连在两块之间，一定需要放在一个块里，然后每次合并的时候更新M和c即可

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int N=1000005;

int n,m,z[N],b[N],c[N],s[N],ans,f[N];

vector<int>v[N];

struct qwe

{

	int u,v,w;

}a[N];

bool cmp(const qwe &a,const qwe &b)

{

	return a.w<b.w;

}

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int zhao(int x)

{

	return f[x]==x?x:f[x]=zhao(f[x]);

}

int main()

{

	n=read(),m=read();

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

		z[i]=read(),f[i]=i,c[i]=1;

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

		a[i].u=read(),a[i].v=read(),a[i].w=read();

	sort(a+1,a+1+m,cmp);

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

		if(a[i].w<=min(b[zhao(f[a[i].u])]+z[c[zhao(f[a[i].u])]],b[zhao(f[a[i].v])]+z[c[zhao(f[a[i].v])]]))

		{

			int fu=zhao(a[i].u),fv=zhao(a[i].v);

			if(fu!=fv)

			{

				f[fu]=fv;

				c[fv]+=c[fu];

				b[fv]=a[i].w;

			}

		}

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

		v[zhao(f[i])].push_back(i);

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

		if(v[i].size())

			ans++;

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

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

		if(v[i].size())

		{

			printf("%d ",v[i].size());

			for(int j=0;j<v[i].size();j++)

				printf("%d ",v[i][j]);

			puts("");

		}

	return 0;

}

巴特西

bzoj 3559: [Ctsc2014]图的分割【最小生成树+并查集】

最新文章

热门文章