POI2011 IMP-Party

wjh15101051's space

卧薪尝胆，厚积薄发。

POI2011 IMP-Party

Date: Fri Sep 21 15:39:07 CST 2018

In Category: NoCategory

Description：

给定一张 $n$ 个点 $m$ 条边的图 $n\equiv 0(mod\ 3)$ ，保证存在一个大小为 $\frac{2}{3}n$ 的团，要求输出一个大小为 $\frac{n}{3}$ 的团。

$1\le n \le 3000$

Solution：

基本思路就是用一个不在团中的点删掉一个在团中的点，最后剩下的就是一个团，那么可以枚举两个点，如果他们之间没有边，那么要么都不在团里，要么一个在一个不在，把他们都删掉，剩下的就是答案。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 3010

bool tag[MAXN];

bool map[MAXN][MAXN];

int main()

{

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

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		map[a][b] = map[b][a] = true;

	}

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

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

			if(!map[i][j] && !tag[i] && !tag[j])

				tag[i] = tag[j] = true;

	int cnt = 0;

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

	{

		if(!tag[i])

		{

			cout << i << " ";

			++cnt;

			if(cnt == n / 3)break;

		}

	}

	puts("");

	return 0;

}

In tag: 玄学

wjh15101051