UVa 1327 King‘s Quest

题目描述国王有NNN个儿子还有NNN个美丽的女孩。每个王子都有自己喜欢的女孩列表可能喜欢多个女孩。巫师已经给出了一个初始的完美匹配方案即每个王子都匹配到了一个他喜欢的女孩且每个女孩只匹配一个王子。现在国王要求对于每个王子找出所有他可以娶的女孩使得在娶了这个女孩之后剩下的王子仍然能够全部匹配到喜欢的女孩即仍然存在完美匹配。输入格式第一行NNN1≤N≤20001 \leq N \leq 20001≤N≤2000表示王子的数量接下来NNN行每行先是一个整数KiK_iKi​表示该王子喜欢的女孩数量接着是KiK_iKi​个不同的整数111到NNN表示喜欢的女孩编号最后一行NNN个不同的整数表示巫师给出的初始匹配方案第iii个数表示王子iii初始匹配的女孩输出格式对于每个王子输出一行首先是一个整数LiL_iLi​表示该王子可以选择的女孩数量接着是LiL_iLi​个整数表示这些女孩的编号顺序任意题目分析问题本质这是一个二分图匹配的扩展问题。我们需要在保持全局完美匹配存在的前提下找出每个王子可以选择的所有女孩。关键观察初始匹配巫师给出的匹配是一个合法的完美匹配可交换性如果一个王子可以换到另一个女孩同时保持全局匹配存在那么这两个匹配关系必须在某种意义上是可交换的图论建模可以将问题转化为有向图中的强连通分量SCC\texttt{SCC}SCC问题算法思路1. 构建有向图我们将王子和女孩都看作图中的节点节点000到N−1N-1N−1表示王子节点NNN到2N−12N-12N−1表示女孩女孩ggg对应节点Ng−1N g - 1Ng−1构建有向边的规则对于王子iii喜欢的每个女孩ggg如果ggg不是他的初始匹配女孩则添加边i→(Ng−1)i \rightarrow (N g - 1)i→(Ng−1)对于每个女孩ggg在初始匹配中匹配给王子iii添加边(Ng−1)→i(N g - 1) \rightarrow i(Ng−1)→i2. 强连通分量SCC\texttt{SCC}SCC的意义在这个有向图中如果王子iii和女孩jjj在同一个强连通分量中那么王子iii可以选择女孩jjj同时通过分量内的边重新调整匹配使得所有王子仍然有匹配3. 求解步骤读入数据并构建有向图使用Tarjan\texttt{Tarjan}Tarjan算法求强连通分量对于每个王子iii初始匹配的女孩一定可以选其他喜欢的女孩ggg可以选当且仅当王子iii和女孩ggg在同一个SCC\texttt{SCC}SCC中算法正确性证明初始匹配的女孩总是可选的不改变匹配如果王子iii和女孩jjj在同一个SCC\texttt{SCC}SCC中那么存在从iii到jjj和从jjj到iii的路径这意味着可以通过SCC\texttt{SCC}SCC内的环来重新分配匹配使得王子iii匹配女孩jjj同时其他王子仍然有匹配复杂度分析节点数2N2N2N最多400040004000边数∑Ki≤200000\sum K_i \leq 200000∑Ki​≤200000Tarjan 算法复杂度O(NE)O(N E)O(NE)完全可行代码实现// Kings Quest// UVa ID: 1327// Verdict: Accepted// Submission Date: 2025-10-16// UVa Run Time: 0.330s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includevector#includealgorithmusingnamespacestd;constintMAXN4005;// 最多 2N 个节点vectorintG[MAXN];// 邻接表intidx[MAXN],low[MAXN],scc_id[MAXN],scc_cnt,ts;// Tarjan 算法相关数组intstk[MAXN],top;// 栈boolin_stk[MAXN];// 标记节点是否在栈中// Tarjan 算法求强连通分量voidtarjan(intu){idx[u]low[u]ts;stk[top]u;in_stk[u]true;for(intv:G[u]){if(!idx[v]){tarjan(v);low[u]min(low[u],low[v]);}elseif(in_stk[v]){low[u]min(low[u],idx[v]);}}if(low[u]idx[u]){intx;do{xstk[--top];in_stk[x]false;scc_id[x]scc_cnt;}while(x!u);scc_cnt;}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;while(cinN){// 初始化图和相关数组for(inti0;i2*N;i){G[i].clear();idx[i]low[i]scc_id[i]0;in_stk[i]false;}scc_cnttstop0;// 读入每个王子的喜好vectorvectorintlike(N);for(inti0;iN;i){intk;cink;like[i].resize(k);for(intj0;jk;j){cinlike[i][j];}}// 读入初始匹配vectorintmatch(N);for(inti0;iN;i){cinmatch[i];}// 构建有向图for(inti0;iN;i){for(intg:like[i]){if(gmatch[i])continue;// 初始匹配不建边// 王子 i - 女孩 gG[i].push_back(Ng-1);}}for(inti0;iN;i){// 女孩 match[i] - 王子 i初始匹配的反向边G[Nmatch[i]-1].push_back(i);}// 求强连通分量for(inti0;i2*N;i){if(!idx[i])tarjan(i);}// 输出答案for(inti0;iN;i){vectorintans;for(intg:like[i]){// 可以选的女孩初始匹配的女孩 或 在同一个 SCC 中的女孩if(gmatch[i]||scc_id[i]scc_id[Ng-1]){ans.push_back(g);}}sort(ans.begin(),ans.end());coutans.size();for(intg:ans){cout g;}cout\n;}}return0;}总结本题通过将二分图匹配问题转化为有向图的强连通分量问题巧妙地解决了在保持全局匹配存在的前提下找出所有可选匹配的问题。这种SCC\texttt{SCC}SCC的建模方法在图论和匹配问题中有着广泛的应用是解决此类问题的经典技巧。关键点在于理解初始匹配提供了图的骨架额外的喜欢关系构成了潜在的可交换路径强连通分量内的节点可以自由交换而不破坏匹配的完整性这种方法的时间复杂度为O(NE)O(N E)O(NE)能够高效处理题目给出的数据规模。