题意分析

题目背景

本题属于组合优化与图论问题，描述如何将学生分配到两个班级，使得班级规模尽可能均衡，且最孤独学生（在班级中不认识的人数最多）的孤独度最小。

核心问题

1. 输入：
   • 学生编号及他们的熟人列表。
   • 熟人关系是双向的（无向图）。
2. 输出：
   • 最小化最孤独学生的孤独度。
   • 班级分配需满足人数差不超过1。

解题思路

1. 图建模

• 邻接矩阵：用矩阵mp[][]表示学生间的熟人关系，mp[i][j]=1表示认识。
• 孤独度计算：学生在班级中不认识的人数。

2. 深度优先搜索（DFS）

• 状态设计：jl[]数组记录当前班级分配，vis[]标记学生所属班级。
• 剪枝策略：
  • 当已选学生数达到$n/2$时，检查孤独度。
  • 递归枚举所有可能的班级分配组合。

3. 孤独度评估

• 遍历班级：统计每个学生在班级中不认识的人数。
• 更新最小值：维护全局最小孤独度jg。

算法实现

代码框架

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
//抄博友好程序 巧妙 背 dfs
int vis[70];
int jl[70];
int mp[70][70];
int n;
int jg;
int lone[70]; 
void check()
{
	//cout<<"check"<<endl;
	memset(vis,0,sizeof(vis));
	memset(lone,0,sizeof(lone));
	for(int i=0;i<(n/2);i++)
	{
		vis[jl[i]]=1;
	}
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if((vis[i]==vis[j])&&(mp[i][j]==0))
			{
				lone[i]++;
				lone[j]++;
			}
		}
	} 
	int tt=0;
	for(int i=1;i<=n;i++)
	{
		//cout<<lone[i]<<endl;
		tt=max(tt,lone[i]);
	}
	jg=min(jg,tt);
	//cout<<"jg "<<jg<<endl;
}
void dfs(int t,int s)
{
	//cout<<"dfs "<<t<<" "<<s<<endl;
	if(t>n)
	{
		//cout<<"by0 "<<t<<" "<<n<<endl;
		return;
	}
	if(s==(n/2))
	{
		check();
		//cout<<"by1 "<<s<<" "<<n/2<<endl;
		return;
	}
	jl[s]=t;
	//cout<<" jl["<<s<<"]="<<t<<endl;
	dfs(t+1,s+1);//巧妙 
	dfs(t+1,s);//巧妙 
}
int main()
{
	jg=10000;
	memset(vis,0,sizeof(vis));
	memset(jl,0,sizeof(jl));
	memset(mp,0,sizeof(mp));
	int a,tn,b;
	n=0;
	while(scanf("%d",&a)!=EOF)
	{
		n++;
		scanf("%d",&tn);
		for(int i=0;i<tn;i++)
		{
			scanf("%d",&b);
			mp[a][b]=mp[b][a]=1;
		}
	}
	//cout<<n<<endl;
	/*
	for(int i=1;i<10;i++)
	{
		for(int j=1;j<10;j++)
		{
			cout<<mp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	dfs(1,0);
	cout<<jg<<endl;
	return 0; 
} 

关键步骤

1. 输入处理：构建邻接矩阵mp表示熟人关系。
2. DFS枚举：递归枚举所有可能的班级分配组合。
3. 孤独度计算：统计每个班级中学生的孤独度，更新最小值。

复杂度分析

• 时间：$O(2^n)$，DFS枚举所有组合。
• 空间：$O(n^2)$，存储邻接矩阵。