题目链接：https://www.vijos.org/p/1048
很多人一看就想出了思路，不就是一个裸的dfs蛮。。。但是。。在n<=50的情况下，朴素会直接tle。。。。。
然后我就开始剪枝，剪了很多地方，然后多过了一个点。。。。。然后我就发现我的剪枝和我的dfs打的不行
然后我们先看看朴素的打法（打法多，我是一种非常原始的朴素算法）
1 bool check(int x,int dep){
2 for(int i=1;i<=dep;i++)
3 if(map[a[i]][x]==1)return 0;
4 return 1;
5 }
6
7 void dfs(int dep,int pos){
8 if(dep==m+1){ans=max(ans,s);return;}
9 if(s+tot[n]-tot[pos-1]<=ans)return;
10 for(int i=1;i<=n,dep-1+n-i+1>=m;i++){
11 if(vis[i]==0&&check(e[i].ord,dep-1)){
12 vis[i]=1;
13 a[dep]=e[i].ord;
14 s+=val[i];
15 dfs(dep+1,i+1);
16 s-=val[i];
17 a[dep]=0;
18 vis[i]=0;
19 }
20 }
21 return ;
22 }
然后我的这个dfs本身就不够优化。。我其实可以换成不扩展深度dep，而是扩展当前的指针pos，代替我原来程序的i
另一个优化的地方，在这个朴素的程序里面也有，就是维护一个前缀和，如果当前值的大小+后面未遍历的所有值<=我们当前的ans，就跳过
然后就是对于是不是有矛盾的判断，我的朴素算法是邻接矩阵来暴力跑个O(n)来判断
这个位置可以优化，我们开一个二维数组en[i][j]，其中i代表初始序号为i的数，en[i][0]存这个i多少有矛盾的人，然后j就是第几个矛盾的人,e[i][j]就是和i有矛盾的第j个人的序号
然后在判断时加一个enm[x]数组，如果enm[x]==0，说明当前x是没有敌人的，然后就把x 的所有敌人的enm[i]++，标记这些人就有敌人了。。。
然后还剩一个优化的地方，就是排序，这个排序的主要作用是配合我们维护前缀和的剪枝，不过排序要注意排序后的序号和输入矛盾两人的序号可能不同，输入矛盾序号是按照最开始的序号来的，所以要稍微处理一下这个细节
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<queue>
5 #include<cmath>
6 #include<algorithm>
7 #include<cstdlib>
8 #define maxn 60
9 using namespace std;
10
11 int n,m,ans,s,sum,val[maxn],a[maxn],vis[maxn];
12 int tot[maxn],en[maxn][maxn],enm[maxn];
13 struct node{
14 int v,ord;
15 }e[maxn];
16
17 int comp(const void*a,const void*b){
18 return (*(struct node*)a).v<(*(struct node*)b).v?1:-1;
19 }
20
21 void dfs(int pos){
22 if(pos==n+1){ans=max(ans,s);return;}
23 if(s+tot[n]-tot[pos-1]<=ans)return;
24 int o=e[pos].ord;
25 if(enm[o]==0){
26 for(int i=1;i<=en[o][0];i++)
27 enm[en[o][i]]++;
28 s+=e[pos].v;
29 dfs(pos+1);
30 s-=e[pos].v;
31 for(int i=1;i<=en[o][0];i++)
32 enm[en[o][i]]--;
33 }
34 dfs(pos+1);
35 }
36
37 int main(){
38 scanf("%d",&n);
39 for(int i=1;i<=n;i++){
40 scanf("%d",&val[i]);e[i].v=val[i];e[i].ord=i;
41 }
42 e[0].v=0x3f3f3f;
43 qsort(e,n+1,sizeof(e[0]),comp);
44 for(int i=1;i<=n;i++){
45 tot[i]=tot[i-1]+e[i].v;
46 }
47 int x,y;
48 while(scanf("%d%d",&x,&y)!=EOF){
49 en[x][++en[x][0]]=y;
50 en[y][++en[y][0]]=x;
51 }
52 dfs(1);
53 printf("%d",ans);
54 }
55
【总结】
DFS的优化着手点：
1.数据排序，加上对未来最大情况判断（本题表现为前缀和）
2.DFS的参数不用dep（选了几个数），而用pos（正在判断第几个数）
3.记录与自己有关系的人，不用邻接矩阵，用list[i][j]表示，list[i][0]为和自己有关系的人的个数