[dfs] Jzoj P4252 QYQ的图

时间:2022-12-17 13:32:28

Description

给你一个n个点,m条边的无向图,每个点有一个非负的权值ci,现在你需要选择一些点,使得每一个点都满足:
如果这个点没有被选择,则与它有边相连的所有点都必须被选择。
问:满足上述条件的点集中,所有选择的点的权值和最小是多少?
QYQ很快就解决了这个问题,但是他已经回到了左下角……没有留下答案,现在只好请你来解决这个问题啦!
 

Input

从文件graph.in中输入数据。
输入的第一行包含两个整数n,m
输入的第二行包含n个整数,其中第i个整数代表ci
输入的第三行到第m+2行,每行包含两个整数u,v,代表点u和点v之间有一条边

Output

输出到文件graph.out中。
输出的第一行包含一个整数,代表最小的权值和
 

Sample Input

3 1
1 2 3
3 1

Sample Output

1
样例说明:
只选择1号点,满足题意
 

Data Constraint

对于20% 的数据:n<=10
对于40%的数据:n<=20
对于100%的数据:1<=n<=50, 1<=m<=500, 0<=c<=1000
图中可能会有重边,自环。
点的编号为1—n。

 

题解

  • 直接搜索,如果一个点不选就把所有它连的点选上,再加上一些最优性剪枝就好了

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #define N 60
 4 using namespace std;
 5 int e[N][N],a[N],c[N],n,m,ans=2147483647;
 6 void dfs(int d,int x,int y)
 7 {
 8     if (d>x) { ans=min(ans,y); return; }
 9     if (a[d]!=0) { dfs(d+1,x,y+(a[d]==1?c[d]:0)); return; }
10     int bz=0;
11     for (int i=1;i<=e[d][0];i++)
12         if (a[e[d][i]]==0) bz=1;
13         else if (a[e[d][i]]==2) { bz=2; break; }
14     if (bz==0) a[d]=2,dfs(d+1,x,y),a[d]=0; 
15     if (bz==1) a[d]=1,dfs(d+1,x,y+c[d]),a[d]=2,dfs(d+1,x,y),a[d]=0;
16     if (bz==2) a[d]=1,dfs(d+1,x,y+c[d]),a[d]=0;
17 }
18 int main()
19 {
20     freopen("graph.in","r",stdin),freopen("graph.out","w",stdout),scanf("%d%d",&n,&m);
21     for (int i=1;i<=n;i++) scanf("%d",&c[i]);
22     for (int i=1,x,y;i<=m;i++)
23     {
24         scanf("%d%d",&x,&y);
25         if (x!=y) e[x][++e[x][0]]=y,e[y][++e[y][0]]=x; else a[x]=1;
26     }
27     dfs(1,n,0),printf("%d",ans);
28 }