当前位置：首页 > news >正文

UVa 1327 King‘s Quest

news 2026/5/4 7:11:00

题目描述

国王有NNN个儿子，还有NNN个美丽的女孩。每个王子都有自己喜欢的女孩列表（可能喜欢多个女孩）。巫师已经给出了一个初始的完美匹配方案，即每个王子都匹配到了一个他喜欢的女孩，且每个女孩只匹配一个王子。

现在国王要求：对于每个王子，找出所有他可以娶的女孩，使得在娶了这个女孩之后，剩下的王子仍然能够全部匹配到喜欢的女孩（即仍然存在完美匹配）。

输入格式

第一行：NNN（1≤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对应节点N+g−1N + g - 1N+g−1）

构建有向边的规则：

对于王子iii喜欢的每个女孩ggg：
- 如果ggg不是他的初始匹配女孩，则添加边i→(N+g−1)i \rightarrow (N + g - 1)i→(N+g−1)
对于每个女孩ggg（在初始匹配中匹配给王子iii）：
- 添加边(N+g−1)→i(N + g - 1) \rightarrow i(N+g−1)→i

2. 强连通分量（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≤200000
Tarjan 算法复杂度：O(N+E)O(N + E)O(N+E)，完全可行

代码实现

// King's Quest// UVa ID: 1327// Verdict: Accepted// Submission Date: 2025-10-16// UVa Run Time: 0.330s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;constintMAXN=4005;// 最多 2N 个节点vector<int>G[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{x=stk[--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(cin>>N){// 初始化图和相关数组for(inti=0;i<2*N;i++){G[i].clear();idx[i]=low[i]=scc_id[i]=0;in_stk[i]=false;}scc_cnt=ts=top=0;// 读入每个王子的喜好vector<vector<int>>like(N);for(inti=0;i<N;i++){intk;cin>>k;like[i].resize(k);for(intj=0;j<k;j++){cin>>like[i][j];}}// 读入初始匹配vector<int>match(N);for(inti=0;i<N;i++){cin>>match[i];}// 构建有向图for(inti=0;i<N;i++){for(intg:like[i]){if(g==match[i])continue;// 初始匹配不建边// 王子 i -> 女孩 gG[i].push_back(N+g-1);}}for(inti=0;i<N;i++){// 女孩 match[i] -> 王子 i（初始匹配的反向边）G[N+match[i]-1].push_back(i);}// 求强连通分量for(inti=0;i<2*N;i++){if(!idx[i])tarjan(i);}// 输出答案for(inti=0;i<N;i++){vector<int>ans;for(intg:like[i]){// 可以选的女孩：初始匹配的女孩 或 在同一个 SCC 中的女孩if(g==match[i]||scc_id[i]==scc_id[N+g-1]){ans.push_back(g);}}sort(ans.begin(),ans.end());cout<<ans.size();for(intg:ans){cout<<" "<<g;}cout<<"\n";}}return0;}