题目描述
FJ 有 \(N\) 个礼物给他的 \(N\) 头奶牛,这 \(N\) 个礼物和 \(N\) 头奶牛都分别按顺序被标记为从 \(1\) 到 \(N\) 的整数。每头奶牛都有一个愿望单,记录着一个含有 \(N\) 个礼物的排列。比起在愿望单中出现更晚的礼物,奶牛更喜欢先出现在愿望单中的礼物。
因为 FJ 太懒了,他直接把 \(i\) 号礼物分配给了 \(i\) 号奶牛。现在,奶牛们聚在了一起,决定重新分配礼物,以便在重新分配后,每头奶牛都能得到跟原来一样,或是它更喜欢的礼物。
对于每个 \(i\)(\(1\le i\le N\)),计算出重新分配后, \(i\) 号奶牛可能拿到的最好的礼物(这个奶牛经过重新分配后能拿到的最喜欢的礼物)。
输入格式
第一行输入 \(N\)。之后 \(N\) 行每行包含一个奶牛的愿望单。保证这 \(N\) 行都是从 \(1\) 到 \(N\) 的排列,即每一行都不按顺序不重不漏地包含 \(1\) 到 \(N\) 中的每个整数。
输出格式
输出 \(N\) 行,第 \(i\) 行输出重新分配后 \(i\) 号奶牛可能得到的最好礼物。
说明/提示
\(2 \sim 3\) 号测试点满足 \(N \le 8\)。对于 \(100\%\) 的数据,满足 \(1 \le N \le 500\)。
分析
前置知识点:Floyd 传递闭包。
Floyd 本身用于求解多源最短路径的问题。其代码如下。
for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
如果我们不记录 \(i\),\(j\) 之间的最短路,而是改为记录 \(i\),\(j\) 之间是否能够到达,我们该怎么做呢?
我们设 \(dis_{i,j}\) 表示 \(i\),\(j\) 之间是否直接到达,满足 \(dis_{i,j} \in \{0,1\}\)。如果 \(i\),\(j\) 之间能够到达,那么两个节点一定满足以下两个条件中至少一个:
其中 \(k\) 为一个中转节点。我们可以用语句表示。即 f[i][j] = f[i][j] || (f[i][k] && f[k][j])
或者 f[i][j] |= f[i][k] & f[k][j]
。于是我们就成功记录了 \(i\),\(j\) 之间是否能够到达。这就是 Floyd 传递闭包。
for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)link[i][j] |= link[i][k] & link[k][j];
对于这道题,如果一个礼物可以到达这个奶牛原本就能拿到的礼物,并且奶牛更喜欢这个礼物,那么答案 \(+1\),否则就继续遍历。如果走到奶牛原本得到的礼物就去统计下一个。代码如下:
#include <iostream>
using namespace std;
using ll = long long;
ll N, m[10005][10005], link[10005][10005];int main(void){cin >> N;for(int i=1; i<=N; ++i)for(int j=1; j<=N; ++j)cin >> m[i][j];for(int i=1; i<=N; ++i)for(int j=1; j<=N; ++j){link[i][m[i][j]] = 1;if(m[i][j] == i)break;}for(int k=1; k<=N; ++k)for(int i=1; i<=N; ++i)for(int j=1; j<=N; ++j)link[i][j] |= (link[i][k] & link[k][j]);for(int i=1; i<=N; ++i)for(int j=1; j<=N; ++j)if(link[i][m[i][j]] && link[m[i][j]][i]){cout << m[i][j] << '\n';break;}return 0;
}