P1692 部落卫队网页链接P1692 部落卫队题目描述原始部落 byteland 中的居民们为了争夺有限的资源经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍希望从部落的居民中选出最多的居民入伍并保证队伍中任何2 22个人都不是仇敌。给定 byteland 部落中居民间的仇敌关系编程计算组成部落卫队的最佳方案。若有多种方案可行输出字典序最大的方案。输入格式第1 11行有2 22个正整数n nn和m mm表示 byteland 部落中有n nn个居民居民间有m mm个仇敌关系。居民编号为1 , 2 , ⋯ , n 1,2, \cdots ,n1,2,⋯,n。接下来的m mm行中每行有2 22个正整数u uu和v vv表示居民u uu与居民v vv是仇敌。输出格式第1 11行是部落卫队的人数文件的第2 22行是卫队组成x i x_ixi​1 ≤ i ≤ n 1 \le i \le n1≤i≤nx i 0 x_i0xi​0表示居民i ii不在卫队中x i 1 x_i1xi​1表示居民i ii在卫队中。输入输出样例 #1输入 #17 10 1 2 1 4 2 4 2 3 2 5 2 6 3 5 3 6 4 5 5 6输出 #13 1 0 1 0 0 0 1说明/提示对于60 % 60\%60%数据n ≤ 20 n \le 20n≤20m ≤ 100 m \le 100m≤100。对于所有数据n ≤ 100 , m ≤ 3000 n \le 100,m \le 3000n≤100,m≤3000。数据从所有合法数据中随机均匀取样。解题思路本题是最大独立集问题。将每个居民视为图中的节点若两人是仇敌则在图中连边。要求选出最多的人使得选中的人之间没有边相连即求该图的最大独立集。由于n ≤ 100 n \le 100n≤100且数据为随机均匀生成可以采用深度优先搜索 剪枝进行求解。1. 问题等价转化建有冲突关系图book[i][j] true表示居民i ii与j jj是仇敌。目标在n nn个居民中选出若干人满足任意两人不是仇敌即被选中的人之间没有边。最大化被选中的人数。输出时用ansf[i] 1表示居民i ii在卫队中0表示不在。若存在多个最大方案需输出字典序最大的方案。2. 算法实现DFS 剪枝使用回溯法枚举每个居民是否被选中并利用剪枝函数提前终止无效搜索。冲突检查在尝试将居民a aa加入当前卫队时遍历已选居民编号 a aa若存在flag[i] book[i][a]则说明a aa与已选居民仇敌不能选择。剪枝条件b n - a ans时直接返回。其中b是当前已选人数自增后n - a是剩余最多还能选择的人数如果当前已选人数加上最大可能的未来人数都不超过已知最优解ans则继续搜索不可能产生更优解提前退出。递归枚举若a aa合法将其加入卫队flag[a] 1然后递归枚举后续居民。回溯时撤销选择flag[a] 0外层循环继续尝试不选择a aa而选择其他居民的分支。更新答案当找到一个人数更多的方案时记录当前方案到ansf。由于搜索顺序优先考虑编号较小的居民第一个找到的最大人数方案即为字典序最大的方案。3. 复杂度分析时间复杂度最坏情况下为O ( 2 n ) O(2^n)O(2n)但剪枝条件大幅减少了搜索空间尤其对于随机图实际运行效率很高可以在可接受时间内处理n ≤ 100 n \le 100n≤100。空间复杂度O ( n 2 ) O(n^2)O(n2)存储冲突矩阵O ( n ) O(n)O(n)存储当前选择状态和最优方案。总结本题通过 DFS 回溯枚举所有可能的选择组合利用冲突检查和最优性剪枝加速搜索同时利用搜索顺序保证了字典序最大的要求。该方法是求解中小规模最大独立集问题的常见有效手段。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,ans,ansf[105];boolbook[105][105],flag[105];voiddfs(ll a,ll b){if(bn-aans)return;for(ll i1;ia;i)if(flag[i]book[i][a])return;flag[a]1;for(ll ia1;in;i)dfs(i,b);if(bans){ansb;for(ll i1;in;i)ansf[i]flag[i];}flag[a]0;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);for(ll i1,a,b;im;i){scanf(%lld%lld,a,b);book[a][b]book[b][a]1;}for(ll i1;in;i)dfs(i,0);printf(%lld\n,ans);for(ll i1;in;i)printf(%lld ,ansf[i]);return0;}