题目大意

有一个n个点的完全图，上面有m条边的权值为1，其余为0

求MST

n,m<=10^5

题解

方法一：

维护一个点集，表示当前MST中的点

一开始任意加一个点

对于一个未加入的点，如果和点集中的点的1边数<点集大小，那么必定有0边

所以用堆维护与点集中点有1边的条数的点，每次取出度数最小的

重点：c++的堆的比较函数不太一样

如果一个点的度数=点集大小，答案+1

之后把这个点加进点集（即覆盖其余的点）

方法二：

暴力bfs，用set维护剩余未加入的点

如果用一个点取扩展其余的点，每个点会被0边覆盖一次，每条1边也只会被找到一次

所以时间是O((n+m)log)的

code

方法一

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <queue>

#define fo(a,b,c) for (a=b; a<=c; a++)

#define fd(a,b,c) for (a=b; a>=c; a--)

#define max(a,b) (a>b?a:b)

using namespace std;

struct type{

	int s,x;

	friend bool operator < (type a,type b) {return a.s>b.s;}

};

priority_queue<type> heap;

int a[200002][2];

int ls[100001];

int b[100001];

int d[100001];

int bz[100001];

int n,m,i,j,k,l,len,ans;

void New(int x,int y)

{

	++len;

	a[len][0]=y;

	a[len][1]=ls[x];

	ls[x]=len;

}

int main()

{

//	freopen("b.in","r",stdin);

	len=1;

	scanf("%d%d",&n,&m);ans=n;

	fo(i,1,m)

	{

		scanf("%d%d",&j,&k);

		New(j,k);

		New(k,j);

	}

	fo(i,1,n)

	heap.push(type{0,i});

	ans=0;

	fo(l,0,n-1)

	{

		if (heap.top().s==l)

		++ans;

		i=heap.top().x;

		bz[i]=1;

		heap.pop();

		for (j=ls[i]; j; j=a[j][1])

		if (!bz[a[j][0]])

		{

			++d[a[j][0]];

			heap.push(type{d[a[j][0]],a[j][0]});

		}

		while (!heap.empty() && heap.top().s<d[heap.top().x])

		heap.pop();

	}

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

}

巴特西

CF1242B. 0-1 MST

题目大意

题解

code

最新文章

热门文章