【JZOJ4252】QYQ的图【搜索】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4252
给你一个$n$个点，$m$条边的无向图，每个点有一个非负的权值$c_i$，现在你需要选择一些点，使得每一个点都满足：如果这个点没有被选择，则与它有边相连的所有点都必须被选择。
问：满足上述条件的点集中，所有选择的点的权值和最小是多少？

---

思路：

$nleq50$。考试时打了一个爆搜，结果90分。。。
卡常一下就过了。就是$2^n$暴力。。。
好像正解就是这样的。因为不选一个点就会影响到很多点的选择，复杂度远远没有那么高。
最坏情况应该是一条链，而链之多选择25个点，所以应该是可过的。

---

代码：

#include <cstdio>
#include <cstring>
using namespace std;

int n,m,a[60],x,y,ans=2e9,tot,head[60],cho[60];
bool v[60];

struct edge
{
	int next,to;
}e[1010];

int read()
{
	int d=0;
	char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9')
		d=(d<<3)+(d<<1)+ch-48,ch=getchar();
	return d;
}

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

void dfs(int x,int s)
{
	if (s>=ans) return;
	if (x>n)
	{
		if (s<ans) ans=s;
		return;
	}
	cho[x]++;  //cho[i]表示点i选择了多少次（因为多少个点不选而必须选）
	dfs(x+1,s+a[x]);
	cho[x]--;
	if (!cho[x])
	{
		int v;
		for (register int i=head[x];~i;i=e[i].next)
		{
			v=e[i].to;
			cho[v]++;
		}
		dfs(x+1,s);
		for (register int i=head[x];~i;i=e[i].next)
		{
			v=e[i].to;
			cho[v]--;
		}
	}
}

int main()
{
	freopen("graph10.in","r",stdin);
	//freopen("graph.out","w",stdout);
	memset(head,-1,sizeof(head));
	n=read(),m=read();
	for (register int i=1;i<=n;i++)
		a[i]=read();
	for (register int i=1;i<=m;i++)
	{
		x=read(),y=read();
		if (x==y&&!v[x])
		{
			ans+=a[x];
			v[x]=1;
			cho[x]++;
		}
		else
		{
			add(x,y);
			add(y,x);
		}
	}
	dfs(1,0);
	printf("%d
",ans);
	return 0;
}