没有任何剪枝，还以为要挂，结果1A了...
测试数据 #0: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 648 KiB, score = 10
测试数据 #3: Accepted, time = 234 ms, mem = 648 KiB, score = 10
测试数据 #4: Accepted, time = 218 ms, mem = 648 KiB, score = 10
测试数据 #5: Accepted, time = 250 ms, mem = 648 KiB, score = 10
测试数据 #6: Accepted, time = 203 ms, mem = 648 KiB, score = 10
测试数据 #7: Accepted, time = 343 ms, mem = 648 KiB, score = 10
测试数据 #8: Accepted, time = 359 ms, mem = 648 KiB, score = 10
测试数据 #9: Accepted, time = 421 ms, mem = 648 KiB, score = 10
Accepted, time = 2074 ms, mem = 648 KiB, score = 100
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;

int n, m;
int disable[150][150];
int ans;
int _ans[150];
int stk[150];

inline void in() {
int a, b, i;
scanf("%d%d", &n, &m);
for(i = 1;i <= n;i ++) disable[i][i] = 1;
for(i = 0;i < m;i ++) {
scanf("%d%d", &a, &b);
disable[a][b] = disable[b][a] = 1;
}
}

void DFS(int x, int depth) {
int i, j, flag;
for(i = x;i <= n;i ++) {
flag = 0;
for(j = 0;j < depth;j ++) {
if(disable[stk[j]][i]) {
flag = 1;
break;
}
}
if(!flag) {
stk[depth] = i;
DFS(i, depth+1);
}
}
if(depth > ans) {
ans = depth;
memset(_ans, 0, sizeof(_ans));
for(i = 0;i < depth;i ++) {
_ans[stk[i]] = 1;
}
}
}

inline void solve() {
int i;
ans = 1;
for(i = 1;i <= n;i ++) {
stk[0] = i;
DFS(i, 1);
}
cout << ans << endl;
for(i = 1;i <= n;i ++) cout << _ans[i] << ' ';
}

int main() {
in();
solve();
return 0;
}
```

暴力AC
测试数据 #0: Accepted, time = 0 ms, mem = 4996 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 5000 KiB, score = 10

测试数据 #2: Accepted, time = 171 ms, mem = 5000 KiB, score = 10

测试数据 #3: Accepted, time = 984 ms, mem = 4996 KiB, score = 10

测试数据 #4: Accepted, time = 984 ms, mem = 4996 KiB, score = 10

测试数据 #5: Accepted, time = 984 ms, mem = 5000 KiB, score = 10

测试数据 #6: Accepted, time = 984 ms, mem = 4996 KiB, score = 10

测试数据 #7: Accepted, time = 953 ms, mem = 4996 KiB, score = 10

测试数据 #8: Accepted, time = 968 ms, mem = 4996 KiB, score = 10

测试数据 #9: Accepted, time = 984 ms, mem = 5000 KiB, score = 10

##**庆祝橙名！！！**

评测姬强硬啊！我的电脑（core m5【雾）随机数据要跑10s，然而。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 620 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 620 KiB, score = 10
测试数据 #3: Accepted, time = 140 ms, mem = 620 KiB, score = 10
测试数据 #4: Accepted, time = 187 ms, mem = 628 KiB, score = 10
测试数据 #5: Accepted, time = 203 ms, mem = 628 KiB, score = 10
测试数据 #6: Accepted, time = 187 ms, mem = 628 KiB, score = 10
测试数据 #7: Accepted, time = 312 ms, mem = 628 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 624 KiB, score = 10
测试数据 #9: Accepted, time = 359 ms, mem = 628 KiB, score = 10

####Accepted, time = 1762 ms, mem = 628 KiB, score = 100

发一个bitset位运算不加排序优化的题解，用bitset表示当前选的和不能选的集合。先预处理出每一个点的仇敌bitset，然后每次只需要或运算连接起来，暴力搜加一个最优化剪枝+可行性剪枝

#include <bits/stdc++.h>
using namespace std;

int fuck[125][125];
int mark[125];
int n, m, x, y;
int ans = 1;
bitset<121> ans_set, tmp, tmp2;
bitset<121> fucks[125];

void dfs(int i, const bitset<121> &bt, const bitset<121> &fail, int cho = 0)
{
        if (n-i+1+cho <= ans) return;
        if (i == n+1 && cho > ans) {
                ans = cho;
                //cout << ans << endl;
                ans_set = bt;
        } if (i == n+1) return;
        if (fail[i] != 1)
                dfs(i+1, bt | (tmp<<i), fail | fucks[i], cho + 1);
        dfs(i+1, bt, fail, cho);
}

int main()
{
        //freopen("date.in", "r", stdin);
        memset(fuck, 0, sizeof fuck);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
                scanf("%d%d", &x, &y);
                fuck[x][y] = fuck[y][x] = 1;
        }
        tmp = 1;
        for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                        if (fuck[i][j])
                                fucks[i] = fucks[i] | (tmp<<j);
        bitset<121> st, fal;
        st = fal = 0;
        dfs(1, st, fal);
        cout << ans << endl;
        for (int i = 1; i <= n; i++)
                cout << ans_set[i] << " ";
        return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,s,a[300][300];
bool b[300],d[300];

void go(int x,int y)
{
if(y+n-x+1<=s)
return;
if(x>n)
{
if(y>s)
{

int j;
s=y;
for(j=1;j<=n;j++)
d[j]=b[j];
}
return;
}
if (!b[x])
{
go(x+1,y);
return;
}
int i,t,c[300];
t=0;
for(i=1;i<=a[x][0];i++)
if(b[a[x][i]])
{
c[++t]=a[x][i];
b[a[x][i]]=false;
}
go(x+1,y+1);
for(i=1;i<=t;i++)
b[c[i]]=true;
b[x]=false;
go(x+1,y);
b[x]=true;
}
int main()
{
cin>>n>>m;
int i,x,y;
for(i=1;i<=m;i++)
{
cin>>x>>y;
if(x<y)
a[x][++a[x][0]]=y;
else
a[y][++a[y][0]]=x;
}
s=0;
memset(b,1,sizeof(b));
go(1,0);
cout<<s<<endl;
for(i=1;i<=n;i++)
cout<<(d[i]==1)<<' ';
cout<<endl;
return 0;
}

怎么写啊， 排了序也剪了枝。怎么还是8000对MS超时啊

我自己随便random的数据都卡，交上来就AC了。。。

看来重要的是pruning要符合 作者的思路 || 作者的随机程序。

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

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

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

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

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

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

为什么神牛都说要冲突少的先搜？ 觉得直觉上和很多题上都是冲突多的先搜嘛。。。

改了若干优化，从vijos_1593.cpp到vijos_1593_V6.cpp，终于V5还是AC了。。

WA 26 次的RP 呀……

我的战绩够辉煌了吧~~

就因为没加排序剪枝？！

质疑机子的稳定性……

怎么剪枝啊？

输入的处理确实十分猥琐

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

强烈要求修改输入数据

极度猥琐

我把ac率降到7%

由把它搞回8%

读入处理（猥琐到爆，浪费了我1个多小时，身心健康受到严重影响）

排序剪枝

开除的人大于最优解时开除的人都时候剪枝

我没有排序

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

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

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

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

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

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

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

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

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

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

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

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

..哎呀呀。终于秒杀。。好久没做题。DFS都会错了呀。。

可能有用的一些话：

数据中有这样的关系：自己和自己是仇敌，而答案是可以把这样的人加入队伍

这个排序剪枝谁都想得出来,

可是排序后原来第一的人就不是第一个人了,

那有怎么保证编号小的在前边呢?

终于知道为什么不加那个搜索剪枝爆搜会WA。

BS出题人,无敌水题!

Orz楼上的神牛。。。。。。

先排个序，得罪人多的往后靠

加一个剪枝就可以：剩下的人都拿上都及不上最优则不搜

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

（右边看到的讨论在哪里的？）

沙茶题留名……

问：我为什么不会做？

答：因为我是沙茶！

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

丫丫 第二个通过了啊啊啊O(∩_∩)O哈哈~

这个要剪3个枝左右

还有对于刚开始读入的时候我就处理了一下数据

偷偷说：“搜索应该依次对于第i个人进行操作 取或者不取

当然要加一些剪枝啊

”

回SKYHACKER:

不是N个1的问题,应该是N的位数大于答案总数的位数

哇~

ORZ 怪盗~基德，唐钰小宝，玛维3位大牛成功秒杀了~

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

其实这道题真的不难……就像楼下教主说的再+一点点剪枝就够了……不用排序剪枝，各位千万别想复杂了……