企业官网建设流程全解析

题目描述

在友好小学一年级，每个学生需要与同班所有不认识的同学进行一分钟的相互介绍。若两个学生原本认识，则无需介绍。为了节省时间，老师希望将NNN名学生分配到两个班级，使得两班人数相差至多111，并且完成全部介绍所需的总时间尽可能短。完成全部介绍的时间定义为所有学生中需要进行的最大介绍次数，因为每个学生可以依次与不认识的同学交谈，而总时间由最繁忙的学生决定。

给定NNN（1≤N≤241 \le N \le 241≤N≤24）以及学生之间的认识关系（无向图），求一种最优分配方案，并输出该方案下每个学生需要进行的最大介绍次数，以及两个班级的具体学生名单。

输入格式

输入包含多个测试用例。各测试用例之间由一个空行分隔。

每个测试用例的第一行为一个整数NNN，表示学生总数。接下来NNN行，每行描述一个学生的认识关系，格式为：

• 学生编号（1∼N1 \sim N1∼N）
• 该学生认识的人数kkk
• 随后kkk个整数，表示该学生认识的学生编号（顺序任意）

数据保证一致性，即若AAA认识BBB，则BBB也认识AAA。

输出格式

对于每个测试用例，输出三行：

1. 第一行输出一个整数，表示最优分配下每个学生需要进行的最大介绍次数。
2. 第二行描述第一个班级：先输出班级人数，再按升序输出该班级所有学生编号，各数字之间用单个空格分隔。
3. 第三行描述第二个班级：格式同第二行。

两个连续测试用例的输出之间用一个空行隔开。若存在多个最优分配，输出任意一组即可。

样例

输入

4 1 2 3 4 2 2 3 4 3 2 1 2 4 2 1 2 2 1 1 2 2 1 1

输出

0 2 1 3 2 2 4 0 1 1 1 2

说明：样例输出中，第一组测试用例的分配结果为：班级一有学生1,31,31,3，班级二有学生2,42,42,4，最大介绍次数为000。第二组测试用例中，两名学生互相认识，分配为每班一人，最大介绍次数也为000。

题目分析

本题核心在于将学生划分为两个集合（班级），使得每个学生在其所在班级内不认识的人数最大值最小。由于N≤24N \le 24N≤24，直接枚举所有可能的分割方案是可行的。

我们用图模型表示认识关系：顶点为学生，边表示相互认识。对于某个分配方案，每个学生iii的“介绍次数”等于他在自己班级内不认识的人数，也就是补图（不认识关系）中，与该学生同属于一个班级的邻居数量。我们需要最小化所有学生介绍次数的最大值。

由于两班人数差至多111，我们可以固定其中一个班级的人数为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉（即较大的班），另一个班级自动为补集。枚举所有大小为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉的子集即可覆盖所有合法分配。

解题思路

1. 数据存储：使用邻接矩阵或位掩码记录认识关系。每个学生iii维护一个整数notKnow[i]，其二进制第jjj位为111表示iii与jjj不认识（i≠ji \ne ji=j）。这样，对于任意班级集合mask，学生iii在该班级内的不认识人数可通过popcount(notKnow[i] & mask)快速得到。

2. 枚举子集：令NNN为总人数，target=⌈N/2⌉target = \lceil N/2 \rceiltarget=⌈N/2⌉。使用Gosper's hack算法高效枚举所有大小为targettargettarget的子集。该算法每次生成下一个包含相同数量111位的整数，时间复杂度O(C(N,target))O(C(N, target))O(C(N,target))，在N=24N=24N=24时，最大组合数为C(24,12)=2,704,156C(24,12)=2,704,156C(24,12)=2,704,156，完全可行。

3. 计算最优值：对于每个子集mask，补集comp = fullMask ^ mask。遍历每个学生iii，若iii属于mask，则其介绍次数为popcount(notKnow[i] & mask)；否则为popcount(notKnow[i] & comp)。记录最大值maxDeg。若maxDeg小于当前最优值，则更新最优值及对应的子集。

4. 输出：根据最优子集，分别整理两个班级的学生编号（升序），按照格式输出最大介绍次数、班级人数和名单。

代码实现

// You Who// UVa ID: 649// Verdict: Accepted// Submission Date: 2026-07-02// UVa Run Time: 0.510s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;boolfirstCase=true;while(cin>>N){// 读入认识关系vector<vector<bool>>know(N,vector<bool>(N,false));for(inti=0;i<N;++i)know[i][i]=true;for(inti=0;i<N;++i){intid,k;cin>>id>>k;--id;for(intj=0;j<k;++j){intv;cin>>v;--v;know[id][v]=know[v][id]=true;}}// 构建每个学生的不认识掩码vector<int>notKnow(N,0);intfullMask=(1<<N)-1;for(inti=0;i<N;++i){intmask=0;for(intj=0;j<N;++j)if(i!=j&&!know[i][j])mask|=(1<<j);notKnow[i]=mask;}inttarget=(N+1)/2;// 较大班级的人数intbestMax=N+1;intbestMask=0;// Gosper's hack: 枚举所有大小为 target 的子集intmask=(1<<target)-1;intlimit=1<<N;while(mask<limit){intcomp=fullMask^mask;intmaxDeg=0;for(inti=0;i<N;++i){intd;if(mask&(1<<i))d=__builtin_popcount((unsigned)(notKnow[i]&mask));elsed=__builtin_popcount((unsigned)(notKnow[i]&comp));if(d>maxDeg)maxDeg=d;}if(maxDeg<bestMax){bestMax=maxDeg;bestMask=mask;}// 生成下一个组合intc=mask&-mask;intr=mask+c;mask=(((r^mask)>>2)/c)|r;}// 输出，两个用例之间空一行if(!firstCase)cout<<'\n';firstCase=false;cout<<bestMax<<'\n';vector<int>classA,classB;for(inti=0;i<N;++i){if(bestMask&(1<<i))classA.push_back(i+1);elseclassB.push_back(i+1);}cout<<classA.size();for(intid:classA)cout<<' '<<id;cout<<'\n';cout<<classB.size();for(intid:classB)cout<<' '<<id;cout<<'\n';}return0;}

总结

本题的关键在于将实际问题转化为图论中的最小化最大内部补图度数问题，并利用NNN较小的特点通过枚举所有合法分割求得最优解。算法复杂度为O(C(N,⌈N/2⌉)⋅N)O(C(N, \lceil N/2 \rceil) \cdot N)O(C(N,⌈N/2⌉)⋅N)，在N≤24N \le 24N≤24时运行效率足够。

• 使用位掩码和Gosper's hack提高了枚举效率，同时简化了内部度数的计算。
• 注意输入可能包含多个测试用例，且输出格式要求空行分隔，需要妥善处理首例空行问题。

该方法属于典型的暴力枚举 + 位运算优化，适用于小规模组合优化问题。