UVa 259 Software Allocation

题目分析一个计算中心有101010台不同的计算机编号000至999每台计算机在同一时间只能运行一个应用程序。有262626种应用程序名称分别为A\texttt{A}A至Z\texttt{Z}Z。每天会有用户提交应用程序同一个应用程序可能被多个用户提交此时需要为每个用户分配一台不同的计算机来运行该应用程序。每天结束后文员会收集所有的应用程序并为每个应用程序列出可以运行的计算机列表然后尝试将每个应用程序分配到一个计算机上使得每台计算机最多只运行一个应用程序。输入文件每天包含一个或多个作业描述每个作业描述的格式为一个大写字母A∼Z\texttt{A} \sim \texttt{Z}A∼Z表示应用程序名称。一个数字1∼91 \sim 91∼9表示提交该应用程序的用户数量。一个空格字符。一个或多个不同的数字0∼90 \sim 90∼9表示该应用程序可以运行的计算机编号。一个分号;作为终止符。一个换行符。每天的不同作业描述之间由一个空行分隔。输入文件以文件结束符结束。输出要求如果能够成功分配则输出101010个字符分别对应计算机000至999上分配的应用程序用-表示该计算机未被分配任何应用程序否则输出一个感叹号!。解题思路问题本质这是一个典型的二分图匹配问题或者更具体地说是一个多重匹配问题。二分图的一侧是计算机节点共101010台。另一侧是应用程序实例节点。由于同一个应用程序可能有多个用户即多个实例我们需要将每个实例看作一个独立的节点。但实际上我们并不需要显式地创建所有实例节点。我们可以将每个应用程序的需求数量作为该应用程序节点的“容量”而计算机节点容量为111。这本质上是一个带容量限制的二分图匹配问题也称为bbb-匹配问题。可行分配的必要条件在开始匹配之前可以先进行一些快速判断以排除明显不可行的情况总实例数不超过计算机总数设S∑i025countiS \sum_{i0}^{25} count_iS∑i025​counti​其中counticount_icounti​是应用程序iii的用户数量。如果S10S 10S10则不可能分配成功因为只有101010台计算机。每个应用程序的可用计算机数量不少于其需求数量对于应用程序iii设cic_ici​为其可以运行的计算机数量如果counticicount_i c_icounti​ci​则也不可能分配成功。这两个条件是必要但不充分的还需要进一步的搜索或匹配算法来验证。算法选择由于数据规模很小计算机只有101010台应用程序只有262626种每个应用程序最多999个用户可以使用深度优先搜索DFS\texttt{DFS}DFS进行回溯求解。具体思路我们按计算机编号000到999的顺序进行决策。对于当前计算机index尝试为其分配一个尚未分配完的应用程序即该应用程序还有未分配的用户实例。如果某应用程序可以运行在当前计算机上即该计算机在其可用列表中并且该应用程序还有剩余需求则将当前计算机分配给该应用程序并递归处理下一台计算机。如果找不到合适的应用程序也可以选择将当前计算机留空不分配任何应用程序然后继续处理下一台计算机。当处理完所有101010台计算机后检查是否所有应用程序的需求都已满足。如果是则找到一组可行解。回溯优化的几个技巧全局变量记录解的状态使用found标志一旦找到解就立即停止搜索。剪枝在进入回溯之前先检查上述两个必要条件。按计算机顺序尝试由于计算机数量固定且很少按顺序分配是直观且高效的。使用candidates数组记录每个应用程序可以运行的计算机总数用于快速判断是否有足够资源。数据结构设计computer[10]一个向量数组computer[i]存储可以运行在计算机iii上的所有应用程序编号0∼250 \sim 250∼25。applications[26]存储每个应用程序的剩余需求数量。candidates[26]存储每个应用程序可以运行的计算机总数预处理时统计。solution[10]存储最终分配结果solution[i]表示计算机iii上运行的应用程序编号−1-1−1表示未分配。输入解析输入文件每天包含多行空行分隔不同的测试案例。解析规则如果读取到空行则执行当前已收集的所有作业描述的分配然后清空数据结构准备处理下一天。如果读取到非空行则解析该行的作业描述第一个字符是应用程序名称。第二个字符是用户数量数字字符。跳过空格后直到分号前的所有数字字符都是可运行的计算机编号。将该应用程序加入对应计算机的可用列表同时更新需求数量。注意输入文件最后可能没有空行所以在读取结束后还需要再调用一次分配函数。代码实现// Software Allocation// UVa ID: 259// Verdict: Accepted// Submission Date: 2016-05-12// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorintcomputer(10);// computer[i] 表示可以在计算机 i 上运行的所有应用程序编号vectorintapplications(26);// applications[i] 表示应用程序 i 当前的剩余需求数量vectorintcandidates(26);// candidates[i] 表示应用程序 i 可以运行的计算机总数vectorintsolution(10);// solution[i] 表示计算机 i 上分配的应用程序编号-1 表示未分配boolfoundfalse;// 是否已经找到可行解// 深度优先搜索回溯函数// index: 当前正在处理的计算机编号0 ~ 9voidbacktrack(intindex){// 已经找到解直接返回if(found)return;// 所有计算机都已处理完毕if(index10){// 检查是否所有应用程序的需求都已满足for(inti0;i26;i)if(applications[i]0)return;// 找到可行解输出结果foundtrue;for(inti0;i10;i){if(solution[i]-1)cout_;elsecout(char)(Asolution[i]);}coutendl;return;}// 尝试为当前计算机分配一个应用程序for(inti0;icomputer[index].size();i){intappcomputer[index][i];// 可以在该计算机上运行的应用程序if(applications[app]0){// 分配该应用程序到当前计算机applications[app]--;solution[index]app;backtrack(index1);// 处理下一台计算机// 回溯恢复状态solution[index]-1;applications[app];// 如果已经找到解立即返回if(found)return;}}// 当前计算机不分配任何应用程序留空backtrack(index1);}// 为当前测试案例进行分配voidallocate(){// 必要条件1应用程序实例总数不能超过计算机数量intcounter0;for(inti0;iapplications.size();i)counterapplications[i];if(counter10){cout!\n;return;}// 必要条件2每个应用程序的可用计算机数量不能少于其需求数量for(inti0;iapplications.size();i)if(applications[i]candidates[i]){cout!\n;return;}// 重置搜索状态并开始回溯foundfalse;fill(solution.begin(),solution.end(),-1);backtrack(0);// 如果回溯结束后仍未找到解则分配失败if(foundfalse)cout!\n;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);fill(candidates.begin(),candidates.end(),0);string line;while(getline(cin,line)){// 空行表示当前测试案例结束if(line.length()0){allocate();// 清空数据结构准备处理下一个测试案例for(inti0;icomputer.size();i)computer[i].clear();fill(applications.begin(),applications.end(),0);fill(candidates.begin(),candidates.end(),0);}else{// 解析作业描述行// 格式: 应用字母 数字 空格 计算机列表 分号charappLetterline[0];intcountline[1]-0;// 用户数量intappIndexappLetter-A;// 更新该应用程序的需求总数applications[appIndex]count;// 解析计算机列表从索引 3 开始直到分号前一个字符for(inti3;iline.length()-1;i){intcomputerIdline[i]-0;// 记录该计算机可以运行的应用程序computer[computerId].push_back(appIndex);// 统计该应用程序可以运行的计算机数量candidates[appIndex];}}}// 处理最后一个测试案例文件末尾可能没有空行allocate();return0;}总结本题的核心是一个小规模的多重二分图匹配问题。由于数据规模极小计算机101010台应用程序262626种使用DFS\texttt{DFS}DFS回溯即可高效求解。代码中通过两个必要条件进行快速剪枝进一步提高了效率。理解本题的关键在于将“每个应用程序可能有多个用户”这一需求转化为带有容量限制的匹配问题并利用回溯搜索找到一组可行分配。