【搜索】JZOJ_4252 QYQ的图

题意

给出一个有$N$N个点$M$M条边的图，每个点有自己的权值。
如果不选某一个点，那么与它相连边的点都要选。
求出选点的最小权值。有重边自环。

思路

直接搜索，按照题目来看是$2^n$2n，显然过不了，但是我们可以加上剪枝，然后就能过了。

代码

#include<cstdio>
#include<algorithm>

struct edgeNode{
	int to, next;
}e[1001];
int n, m, tot, ans;
int head[51], c[51], v[51];

void add(int u, int v) {
	e[++tot].to = v;
	e[tot].next = head[u];
	head[u] = tot;
}

void dfs(int p, int sum) {
	if (sum >= ans) return;
	if (p > n) {
		ans = sum;
		return;
	}
	v[p]++;//表示当前这个点被选了几次，因为下面需要减去
	dfs(p + 1, sum + c[p]);
	v[p]--;
	if (!v[p]) {
		for (int i = head[p]; i; i = e[i].next)
			v[e[i].to]++;
		dfs(p + 1, sum);
		for (int i = head[p]; i; i = e[i].next)
			v[e[i].to]--;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &c[i]);
	for (int i = 1, x, y; i <= m; i++) {
		scanf("%d %d", &x, &y);
		if (x == y) {
			v[x]++;
			ans += c[x];
			continue;
		}
		add(x, y);
		add(y, x);
	}
	ans = 2147483647;
	dfs(1, 0);
	printf("%d", ans);
}