|
|
|
|
|
## [$POJ1904$ $King's$ $Quest$](http://poj.org/problem?id=1904)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
有$n$个王子，每个王子都有$k$个喜欢的妹子，每个王子只能和喜欢的妹子结婚。现有一个匹配表，将每个王子都与一个自己喜欢的妹子配对。请你根据这个表得出每个王子可以和几个自己喜欢的妹子结婚，按序号升序输出妹子的编号，这个表应满足所有的王子最终都有妹子和他结婚（一个妹子只能嫁给一个王子）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
看到题目时，一脸懵逼，只觉得题面很有(`ci`)趣(`ji`)
|
|
|
|
|
|
|
|
|
|
|
|
但没办法啊，为了王国的一夫一妻制我们只好努力啊~awa~
|
|
|
|
|
|
|
|
|
|
|
|
让我们首先来考虑建图
|
|
|
|
|
|
|
|
|
|
|
|
- 如果王子$u$喜欢妹子$v$那我们可以从$u$向$v$连一条有向边
|
|
|
|
|
|
|
|
|
|
|
|
- 如果妹子$v$可以与王子$u$配对（即在配对表上），那我们可以从$v$向$u$连一条有向边
|
|
|
|
|
|
|
|
|
|
|
|
对于样例
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
4
|
|
|
|
|
|
2 1 2
|
|
|
|
|
|
2 1 2
|
|
|
|
|
|
2 2 3
|
|
|
|
|
|
2 3 4
|
|
|
|
|
|
1 2 3 4
|
|
|
|
|
|
```
|
|
|
|
|
|
我们建出了这样一张图：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
红的是王子，蓝的是妹子，绿的表示从王子到公主，黄的表示从妹子到王子
|
|
|
|
|
|
|
|
|
|
|
|
仔细观察我们发现了这张图的一些特别之处：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
每个紫色框出的部分都是个 **强连通分量**！
|
|
|
|
|
|
|
|
|
|
|
|
这意味着什么？
|
|
|
|
|
|
|
|
|
|
|
|
这说明 **这个分量内的每个王子和这个分量内的每个妹子都可以随意匹配**
|
|
|
|
|
|
|
|
|
|
|
|
**答案只需要枚举王子和他所在分量内的妹子即可**
|
|
|
|
|
|
|
|
|
|
|
|
而这个强连通分量又该咋求呢？
|
|
|
|
|
|
|
|
|
|
|
|
当然就是$tarjan$啦
|
|
|
|
|
|
|
|
|
|
|
|
> - $UVA$的题目是有多组数据的，$POJ$的每个点只有一组数据，下面的的代码以多组数据为例，但$POJ$上也能过
|
|
|
|
|
|
|
|
|
|
|
|
> - 代码中王子编号$1..n$，妹子编号$n+1..2n$
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <iostream>
|
|
|
|
|
|
#include <algorithm>
|
|
|
|
|
|
#include <cstring>
|
|
|
|
|
|
#include <stack>
|
|
|
|
|
|
#include <cstdio>
|
|
|
|
|
|
#include <vector>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 4010, M = N * N; // 这个M太BT了！黄海就WA到这里！我一直尝试 M= N<<1, M = N<<2,结果一直错错错！
|
|
|
|
|
|
|
|
|
|
|
|
int n, m; // n个王子，n个姑娘，每个王子喜欢m个姑娘
|
|
|
|
|
|
|
|
|
|
|
|
// 链式前向星
|
|
|
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// tarjan算法求强连通分量
|
|
|
|
|
|
int stk[N], top; // tarjan算法需要用到的堆栈
|
|
|
|
|
|
bool in_stk[N]; // 是否在栈内
|
|
|
|
|
|
int dfn[N]; // dfs遍历到u的时间
|
|
|
|
|
|
int low[N]; // 从u开始走所能遍历到的最小时间戳
|
|
|
|
|
|
int ts; // 时间戳,dfs序的标识,记录谁先谁后
|
|
|
|
|
|
int id[N], scc_cnt; // 强连通分量块的最新索引号
|
|
|
|
|
|
int sz[N]; // sz[i]表示编号为i的强连通分量中原来点的个数
|
|
|
|
|
|
void tarjan(int u) {
|
|
|
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
|
|
|
stk[++top] = u;
|
|
|
|
|
|
in_stk[u] = 1;
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
|
|
|
int j = e[i];
|
|
|
|
|
|
if (!dfn[j]) {
|
|
|
|
|
|
tarjan(j);
|
|
|
|
|
|
low[u] = min(low[u], low[j]);
|
|
|
|
|
|
} else if (in_stk[j])
|
|
|
|
|
|
low[u] = min(low[u], dfn[j]);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
if (dfn[u] == low[u]) {
|
|
|
|
|
|
++scc_cnt; // 强连通分量的序号
|
|
|
|
|
|
int x; // 临时变量x,用于枚举栈中当前强连通分量中每个节点
|
|
|
|
|
|
do {
|
|
|
|
|
|
x = stk[top--]; // 弹出节点
|
|
|
|
|
|
in_stk[x] = false; // 标识不在栈中了
|
|
|
|
|
|
id[x] = scc_cnt; // 记录每个节点在哪个强连通分量中
|
|
|
|
|
|
sz[scc_cnt]++; // 这个强连通分量中节点的个数+1
|
|
|
|
|
|
} while (x != u);
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
|
|
|
freopen("POJ1904.in", "r", stdin);
|
|
|
|
|
|
#endif
|
|
|
|
|
|
|
|
|
|
|
|
while (~scanf("%d", &n)) { // n个王子，n个姑娘
|
|
|
|
|
|
memset(h, -1, sizeof h); // 初始化链式前向星
|
|
|
|
|
|
memset(dfn, 0, sizeof dfn);
|
|
|
|
|
|
memset(low, 0, sizeof low);
|
|
|
|
|
|
memset(id, 0, sizeof id);
|
|
|
|
|
|
memset(in_stk, 0, sizeof in_stk);
|
|
|
|
|
|
memset(stk, 0, sizeof stk);
|
|
|
|
|
|
memset(sz, 0, sizeof sz);
|
|
|
|
|
|
idx = top = scc_cnt = ts = 0;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
scanf("%d", &m); // i号王子喜欢几个姑娘
|
|
|
|
|
|
for (int j = 1; j <= m; j++) { // 是哪几位姑娘
|
|
|
|
|
|
int x;
|
|
|
|
|
|
scanf("%d", &x);
|
|
|
|
|
|
add(i, x + n); // 从王子向妹子连边,建图技巧：(1,n),(n+1,2n)
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
int x;
|
|
|
|
|
|
scanf("%d", &x);
|
|
|
|
|
|
add(x + n, i); // 从妹子向王子连边
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 注意：图中的点是2*n了，每个王子、姑娘都要占一个点
|
|
|
|
|
|
for (int i = 1; i <= 2 * n; i++)
|
|
|
|
|
|
if (!dfn[i]) tarjan(i); // 跑tarjan
|
|
|
|
|
|
|
|
|
|
|
|
for (int u = 1; u <= n; u++) { // 枚举王子
|
|
|
|
|
|
vector<int> ans;
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) { // 枚举王子喜欢的妹子
|
|
|
|
|
|
int v = e[i];
|
|
|
|
|
|
if (id[u] == id[v]) ans.push_back(v - n); // 判断王子和妹子是否在同一强连通分量中
|
|
|
|
|
|
}
|
|
|
|
|
|
printf("%d ", ans.size()); // 这里一定要注意使用%d,黄海写成%lld一直WA到哭
|
|
|
|
|
|
sort(ans.begin(), ans.end()); // 要求按妹子编号升序输出
|
|
|
|
|
|
for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]); // 每个王子的可匹配妹子数
|
|
|
|
|
|
puts("");
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
