2015四川省赛 D Vertex Cover 搜索

题意:

给出一个\(n\)个点\(m\)条边的无向图,现在要给若干个点染色,使得每条边都至少邻接一个被染色的顶点.问至少要给多少各点染色才能满足条件.

分析:

注意到题目中有一个很特殊的条件:

对于图中任意一条边\(u,v\),有\(min \{ u,v \} \leq 30\)

所以最坏的情况下,最多染30个点就可以满足条件.

所以用bitset维护一下当前被染色的点的情况即可.

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <bitset>

using namespace std;

const int maxn = 30;

bitset<500> g[maxn];

int n, m, tot, ans;

void dfs(int d, bitset<500> t) {

	int cnt = t.count();

	if(cnt >= ans) return ;

	if(d == tot) {

		ans = min(ans, cnt);

		return ;

	}

	if(t[d]) dfs(d + 1, t);

	else {

		t[d] = 1;

		dfs(d + 1, t);

		t[d] = 0;

		dfs(d + 1, t | g[d]);

	}

}

int main()

{

	while(scanf("%d%d", &n, &m) == 2) {

		tot = min(30, n);

		for(int i = 0; i < tot; i++) g[i].reset();

		while(m--) {

			int x, y; scanf("%d%d", &x, &y);

			x--; y--;

			if(x > y) swap(x, y);

			g[x][y] = 1;

			if(y < tot) g[y][x] = 1;

		}

		bitset<500> t;

		t.reset();

		ans = tot;

		dfs(0, t);

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

	}

	return 0;

}

巴特西

2015四川省赛 D Vertex Cover 搜索

题意:

分析:

最新文章

热门文章