贪心为什么是错解,没有想明白!
查看原帖
贪心为什么是错解,没有想明白!
183603
SUNCHAOYI废物生成器楼主2020/9/6 12:31

贪心只有 90pts90pts,看了看题解说是错解,但似乎都没有讲明白。所以来求一组 hack 数据或是讲讲错在了哪里!

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 305;
int n,p,ans;
vector <int> v[MAX]; 
bool vis[MAX];
void work ();
int search (int x);
void out (int x);
int main ()
{
	//freopen ("infectious.in","r",stdin);
	//freopen ("infectious.out","w",stdout);
	scanf ("%d%d",&n,&p);
	for (int i = 1;i <= p;++i)
	{
		int x,y;scanf ("%d%d",&x,&y);
		if (x > y) swap (x,y);
		v[x].push_back (y);
	}
	work ();
	for (int i = 1;i <= n;++i)
		if (!vis[i]) ++ans;
	printf ("%d\n",ans);
	return 0;
}
void work ()
{
	queue <int> q,qq;
	qq.push (1); 
	while (!qq.empty ())
	{
		while (!qq.empty ()) q.push (qq.front ()),qq.pop ();
		vector <int> p;
		int sum = 0,k;
		while (!q.empty ())
		{
			int x = q.front ();
			q.pop ();
			for (int i = 0;i < v[x].size ();++i)
			{
				int w = search (v[x][i]);
				if (w > sum) sum = w,k = v[x][i];
				p.push_back (v[x][i]);
			}	
		}
		out (k);
		for (int i = 0;i < p.size ();++i)
		{
			if (p[i] == k) continue;
			qq.push (p[i]);	
		}
	}
}
int search (int x)
{
	int s = 1;
	if (v[x].size () == 0) return 1; 
	for (int i = 0;i < v[x].size ();++i)
		s += search (v[x][i]);
	return s;
}
void out (int x)
{
	vis[x] = 1;
	if (v[x].size () == 0) return ;
	for (int i = 0;i < v[x].size ();++i) out (v[x][i]);
}
2020/9/6 12:31
加载中...