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

P8186 [USACO22FEB] Redistributing Gifts S 题解 - 符星珞

题目描述

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\) 之间能够到达,那么两个节点一定满足以下两个条件中至少一个:

\[\begin{cases} dis_{i,j} = 1\\ dis_{i,k} = 1 \wedge dis_{k,j} = 1\\ \end{cases}\]

其中 \(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;
}
http://www.hskmm.com/?act=detail&tid=30329

相关文章:

  • Windows续
  • uml九类例图详解
  • 继续学习,争取早日找到实习 - Irving11
  • Keil MDK 将不同文件中的特定数据链接到同一位置
  • 1013日总结
  • 数据流图
  • 2025公众号排版效率榜:5款AI工具实测对比,从排版到分发一站搞定
  • OpenLayers地图交互 -- 章节十六:双击缩放交互详解 - 教程
  • CF1935E Distance Learning Courses in MAC
  • 联考の记录
  • 06-mysql备份实战 #
  • 静态内部类
  • 05_mysql备份方案
  • 实验1_CPP
  • 数组
  • CF2153 Codeforces Round 1057 (Div. 2) 游记
  • 从《花果山》到《悬鉴》:一首诗的蜕变与AI元人文理论的建构历程
  • java循环
  • 10.13做题笔记
  • java语法(switch)
  • 详细介绍:微服务与面向服务编程(SOA)入门指南:从架构演进到 Spring Cloud 实践(初学者友好版)
  • python中修改局部json的思路
  • LSNet
  • Webpack 构建速度优化
  • [模拟赛] 过关(pass)
  • 2025.10.13
  • 第十三节:基于 Redis+MQ+DB实现高并发秒杀下的扣减
  • c++初体验
  • 元宇宙的搜索引擎:如何在虚拟世界中查找信息 - 详解
  • 四则运算错题本和错题重做的建立