#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    int n,ans,a[50],num[50],rk[50],sum[50];
    ll cf[50];
    
    void qs(int l,int r)
    {
        int i=l,j=r;
        for (int mid=a[(l+r)>>1];i<j;)
        {
            while (a[i]>mid)
                i++;
            while (a[j]<mid)
                j--;
            if (i<=j)
            {
                swap(a[i],a[j]);
                swap(num[i],num[j]);
                i++,j--;
            }
        }
        if (l<j)
            qs(l,j);
        if (i<r)
            qs(i,r);
    }
    
    void dfs(int pos,ll sta,int cnt)
    {
        if (pos<n)
        {
            if (cnt+sum[n-1]-sum[pos-1]<=ans)
                return;
            if (!(sta&cf[pos]))
                dfs(pos+1,sta|((ll)1<<pos),cnt+a[pos]);
            dfs(pos+1,sta,cnt);
        }
        ans=max(ans,cnt);
    }
    
    void main()
    {
        scanf("%d",&n);
        for (int i=0;i<n;i++)
            scanf("%d",&a[i]),num[i]=i;
        qs(0,n-1);
        for (int i=0;i<n;i++)
            rk[num[i]]=i;
        memset(cf,0,sizeof(cf));
        for (int x,y;~scanf("%d%d",&x,&y);)
        {
            x--,y--;
            cf[rk[x]]|=((ll)1<<rk[y]);
            cf[rk[y]]|=((ll)1<<rk[x]);
        }
        sum[0]=a[0];
        for (int i=1;i<n;i++)
            sum[i]=sum[i-1]+a[i];
        ans=0;
        dfs(0,(ll)0,0);
        printf("%d\n",ans);
    }
}

int main()
{
    dts::main();
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
int ans, n, list[55][55], sum[55], enemy[55], after[55];
struct node
{
    int id;
    int weight;
}member[55];
inline bool cmp(node x, node y)
{
    return x.weight > y.weight;
}
inline void dfs(int x, int now)
{
    if(now + sum[n] - sum[x-1] < ans) return;//剪枝 
    if(x == n + 1)  
    {
        ans = max(ans, now);
        return;
    }
    if(!enemy[x]) //判断此节点与以加节点是否为仇敌 
    {
        for (int i = 1; i <= list[x][0]; i++) //记录此节点仇敌 
            enemy[list[x][i]]++;
        dfs(x + 1, now + member[x].weight);//加入此节点 
        for (int i = 1; i <= list[x][0]; i++) //回溯 
            enemy[list[x][i]]--;
    }
    dfs(x+1, now);//不加入此节点 
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> member[i].weight;
        member[i].id = i;
    }        
    sort(member + 1, member + n + 1, cmp);
    for (int i = 1; i <= n; i++)//记录原来id的新id 
        after[member[i].id] = i;
    int x, y;
    while(cin >> x >> y)//用邻接表记录敌人 
    {
        list[after[x]][++list[after[x]][0]] = after[y];
        list[after[y]][++list[after[y]][0]] = after[x];
    }   
    for (int i = 1; i <= n; i++)//记录前序和 
        sum[i] = sum[i - 1] + member[i].weight;
    dfs(1, 0);
    cout << ans; 
}

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct node{
int to,nxt;
}edg[5000];
struct np{
int a,l;
}elf[55];
int head[55],num,maxS,sumf[55];
int cmp(const np &a,const np &b){
return a.a>b.a;
}
int vis[55];
inline void lock(int x){
int t=head[x];
while(t!=0){
vis[edg[t].to]++;
t=edg[t].nxt;
}
}
inline void unlock(int x){
int t=head[x];
while(t!=0){
vis[edg[t].to]--;
t=edg[t].nxt;
}
}
void dfs(int loc,int sum){
maxS=max(maxS,sum);
if(vis[elf[loc].l]) {
// lock(elf[loc].l);
dfs(loc+1,sum);
// unlock(elf[loc].l);
return;
}
if(sum+sumf[n]-sumf[loc-1]<maxS)
return;
if(loc==n+1)
return;

vis[elf[loc].l]=1;
lock(elf[loc].l);
dfs(loc+1,sum+elf[loc].a);
unlock(elf[loc].l);
vis[elf[loc].l]=0;
dfs(loc+1,sum);

}
void add_e(int a,int b){
edg[++num].nxt=head[a];
edg[num].to=b;
head[a]=num;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("2.txt","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&elf[i].a);
elf[i].l=i;
}
sort(elf+1,elf+n+1,cmp);
for(int i=1;i<=n;i++)
sumf[i]=sumf[i-1]+elf[i].a;
int x,y;
while(cin>>x>>y){
add_e(x,y);
add_e(y,x);
}
dfs(1,0);
cout<<maxS;
return 0;
}

http://blog.csdn.net/fop_zz/article/details/65628328
36ms过所有点

这道题..直接写了个暴力dfs，先按照w[]排个序然后直接裸的dfs,然后卡住0.25这个时间，然后就。。
评测结果
编译成功
测试数据 #0: Accepted, time = 265 ms, mem = 580 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 265 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 580 KiB, score = 10
测试数据 #7: Accepted, time = 171 ms, mem = 580 KiB, score = 10
测试数据 #8: Accepted, time = 265 ms, mem = 580 KiB, score = 10
测试数据 #9: Accepted, time = 265 ms, mem = 580 KiB, score = 10
Accepted, time = 1246 ms, mem = 584 KiB, score = 100
好吧还是写正解不能再水了..

bitset+hash+记忆化搜索
跻身解题1000强留念。。
编译成功

测试数据 #0: Accepted, time = 234 ms, mem = 374992 KiB, score = 10
测试数据 #1: Accepted, time = 265 ms, mem = 374988 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 374992 KiB, score = 10
测试数据 #3: Accepted, time = 265 ms, mem = 374992 KiB, score = 10
测试数据 #4: Accepted, time = 265 ms, mem = 374988 KiB, score = 10
测试数据 #5: Accepted, time = 265 ms, mem = 374984 KiB, score = 10
测试数据 #6: Accepted, time = 281 ms, mem = 374992 KiB, score = 10
测试数据 #7: Accepted, time = 265 ms, mem = 374992 KiB, score = 10
测试数据 #8: Accepted, time = 281 ms, mem = 374988 KiB, score = 10
测试数据 #9: Accepted, time = 296 ms, mem = 374988 KiB, score = 10

【慢大概是慢在开hash空间上了。。否则小数据为何会。。】

Accepted, time = 2667 ms, mem = 374992 KiB, score = 100
思路简单，实现还是要小心。。
另外，自然溢出的hash策略很好用啊。。
```c++
#include <bits/stdc++.h>
using namespace std;

inline unsigned int bithash(const bitset<51> &bi)
{
unsigned int ans = 0;
for (int i = 1; i <= 50; i++) {
if (bi[i])
ans = (ans + (1<<(i-1)))%2333333;
//cout << ans << endl;
}
return ans;
}

struct p {
int next;
bitset<51> bits;
int val;
}edge[23333333];
int bith[2333333], top = 0;
inline void push(const bitset<51> &bits, int val)
{
int i = bithash(bits);
edge[++top].bits = bits;
edge[top].next = bith[i];
edge[top].val = val;
bith[i] = top;
}
inline int val(const bitset<51> &bits)
{
int h = bithash(bits);
for (int i = bith[h]; i; i = edge[i].next)
if (edge[i].bits == bits)
return edge[i].val;
return -1;
}
bitset<51> agst[51], temp[51];
int a[51], n, ans = 0, sum[51];

int dfs(int i, const bitset<51> &bit, int al)
{
if (bit == 0) return 0;
if (i == n+1) return -10000;
//cout << i << " " << bit << " " << al << endl;
int d = val(bit);
if (d != -1)
return d;
if (sum[i] + al <= ans) return -10000;
int tmp = dfs(i+1, bit&(~temp[i]), al);
if (bit[i])
tmp = max(tmp, dfs(i+1, bit&(~agst[i]), al+a[i])+a[i]);
push(bit, tmp);
return tmp;
}

int ta[51], rk[51], op[51];
bool cmp(int i, int j)
{
return ta[i] > ta[j];
}

int main()
{
//cout << pow2mod(50, 1200) << endl;
memset(bith, 0, sizeof bith);
cin >> n;
bitset<51> tmp = 0;
for (int i = 1; i <= n; i++) {
cin >> ta[i];
rk[i] = i;
}
sort(rk+1, rk+n+1, cmp);
sort(ta+1, ta+n+1, greater<int>());
for (int i = 1; i <= n; i++) op[rk[i]] = i;
for (int i = 1; i <= n; i++) {
a[i] = ta[i];
agst[i] = 0;
agst[i][i] = 1;
tmp[i] = 1;
temp[i] = 0;
temp[i][i] = 1;
}
int x, y;
sum[n+1] = 0;
for (int i = n; i >= 1; i--)
sum[i] = sum[i+1]+ta[i];
while (cin >> x >> y) {
x = op[x];
y = op[y];
agst[x][y] = agst[y][x] = 1;
}
cout << dfs(1,tmp, 0) << endl;
return 0;
}
```
做搜索题一定要有点函数式编程的思路，~~因为这样可以攒Rp【误】~~

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 284 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 288 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 284 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 288 KiB, score = 10
测试数据 #9: Accepted, time = 7 ms, mem = 284 KiB, score = 10
Accepted, time = 84 ms, mem = 288 KiB, score = 100

终于ac，此时的我是颓废的。。。我估计思路应该和楼下差不多，不过还是说一下核心叭~
这一题绝对是dfs不解释，问题就在于，如果算法过于朴素很容易超时，所以要加一个剪枝：若 当前和+后面所有值<当前最大值 则 剪枝 ， 大概步骤如下
1.全局变量int now, max, left[51]（c++从0数起）, cannot[51]与bool flag。left[51]数组是预处理的，表示对于第i个精灵，left[i]表示他后面的所有精灵质量的和，cannot[51]表示对于第i个精灵，在搜索时与别人冲突的次数，这里为什么不用bool型而用int呢？因为如果在这一次搜索中第i个精灵有冲突，回溯时不能简单的把cannot[i]从true修改成false，因为可能前面的精灵可能也与第i个精灵有冲突！now表示搜索到现在已经有的全部精灵的和，max是目前最大的。flag的用途一会讲
2.在开始搜索前一定要把精灵质量从大到小排（快排打顺的同学注意了！），这样可以大大减少运行时间，然后开始写dfs函数的代码，这里只给出代码思路
### Block code
void dfs(int a) { // a表示现在正在处理第a个小精灵
if (a == n + 1) { // 递归边界
if (max < now) {
max = now;
}
return;
}
now += qua[a]; // now加上第a个精灵的质量，qua是quality的缩写
if (now + left[a] < max) {
flag = true; // 这个特别重要，在第3点里面解释
now -= qua[a]; // 回溯
return;
}
// 对于每一个与第a个精灵冲突的第i个精灵，cannot[i]自增 1，此处代码略去
for (int i = a + 1; i <= n + 1; ++i) { // 从a后面的第一个精灵开始
if (flag) {
flag = false; // 正如我所说，flag特别重要将在第3点解释，先无视掉这个if
break;
}
if (cannot[i]) { // 如果这个精灵已经有冲突了则不予以考虑
continue;
}
dfs(i);
}
now -= qua[a]; // 回溯
// 对于每一个与a精灵冲突的第i个精灵，cannot[i]自减 1，此处代码略去
}
3.现在就是要说flag的重要性！之前说要加一个“若 当前和+后面所有值的和 < 当前最大值 则 剪枝“的一个剪枝，那到底怎么剪枝？举个例子，这里有四个数：4， 3， 2， 1， 要求你从中挑出若干个数使其和为11，而你选择了dfs，处理到1时，你发现尽管全部加起来了也无法到达11那么大。那么回溯到2，没别的操作了，又回溯到3，此时2已经处理过了，所以要处理1，可是既然刚刚连4+3+2+1都小于11，那4+3+1就更不可能了，那么就要剪枝！
这可能是个不恰当的例子不过确实有助于理解，回到这个问题来，当你发现now+left[a] < max时，就说明到了刚说的”4+3+2+1<11“的情况了，此时应果断回溯，回溯前别忘了now值要减掉第a个精灵的质量，最重要的是，别忘了把flag设为true！！！！此时你顺着程序的思路走，现在应该要回溯到上一层递归的那个循环体里面了！下一次循环，就是想试验”4+3+1“，根据刚刚说的，这是没意义的，所以if(flag) break;这就是正解，跳出循环就不会进行没有必要的搜索了，这也是为什么要把精灵质量从大到小排（原因自己想咯）

p.s.请问那些秒杀的是怎么做到的？？感觉不能再快了啊？？

时间上很难看地过了
朴素搜索只有50分左右
加了一个剪枝70分，第一个点与后两个点过不了。剪枝思路如下：若 当前和+后面所有值的和 < 当前最大值 则剪枝。其中，“后面所有值的和”是预处理放在一个数组里的，简单的说就是后缀和。
于是加了一个排序，值大的放前面，这样可以使上述剪枝更能发挥作用，AC，第一个点用时700ms~800ms。

需要注意状态的备份与恢复、以及排序后精灵的编号。
代码80+

不排序直接用剪枝：当前质量+剩余可取质量<max
可以过，第一组数据大概在1S左右徘徊。

排序的好处貌似是可以尽快踢掉一些质量高的却不符合规则的小精灵，从而使DFS在更早的时候剪枝？

总感觉剪枝很拿不准，万一什么地方考虑不好就超时了

话说这不就是个有限制性的背包...

var
max,n,i,j,t,s,x,y:longint;
a,c,b:array[0..100] of longint;
p:array[0..100] of boolean;
f:array[0..100,0..100] of longint;
procedure find(k,s:longint);
var i:longint;
begin
if s>max then max:=s;
if k>n then exit;
if s+c[k]<max then exit;
for i:=1 to f[b[k],0]+1 do
if p[f[b[k],i]]=false then break;
if i<>f[b[k],0]+1 then find(k+1,s)
else
begin
find(k+1,s);
p[b[k]]:=false; find(k+1,s+a[k]); p[b[k]]:=true;
end;
end;

begin
readln(n);
for i:=1 to n do
begin
read(a[i]); s:=s+a[i];
b[i]:=i;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[j]>a[i] then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
end;
c[0]:=s;
for i:=1 to n do
c[i]:=c[i-1]-a[i-1];
while not(eof) do
begin
readln(x,y);
inc(f[x,0]); f[x,f[x,0]]:=y;
inc(f[y,0]); f[y,f[y,0]]:=x;
end;
fillchar(p,sizeof(p),true);
find(1,0);
writeln(max);
end.

点击查看程序源码+详细题解

一开始：

剪枝：

1.当前质量+剩余可取质量

有没有人不是用搜索做的？

第一次：

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：30 有效耗时：0ms

var c:array[1..50]of boolean;

b:array[1..50,1..50]of boolean;

a,d:array[1..50]of longint;

m,i,n,x,y,max:longint;

function ss(n:longint):boolean;

var i,j:longint;

begin

for i:=1 to n-1 do

if not(b[d[i],d[n]]) then exit(false);

exit(true);

end;

procedure asd(step,s,j:longint);

var i:longint;

begin

if step=m+1 then begin

if (max

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

排序写错了

把排序去掉后发现也能AC

我囧

后来改了下排序 秒杀

编译通过...

├ 测试数据 01：答案正确... 212ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：371ms

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：237ms

第一个点是什么啊？

用邻接矩阵总算还是过了

编译通过...

├ 测试数据 01：答案正确... 259ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：466ms

从大到小排序.

剪枝1:后面所有能访问的点价值总和+现在的价值