c++ T321797 传炸弹

Question

传炸弹

题目描述

小王bot进群后和群友玩起了一个 “传炸弹” 的游戏。

群内包括小王bot在内的 $n$ 个人中每个人都对所有人（包括自己）有一个仇恨值，用矩阵 $a$ 表示。

其中，第 $i$ 个人对第 $j$ 个人的仇恨值为 $a_{i,j}$

保证对于所有 $i$ ，$a_{i,1}$ 到 $a_{i,n}$ 构成一个 $1$ 到 $n$ 的排列。

另外，每个人都有若干个下家，每次传递炸弹只能向自己的下家中的一个传递。（保证下家中没有自己，不能不传）

炸弹初始在编号为 $1$ 的玩家的手中，并且有一个参数 $t$ ，表示炸弹将在传递 $t$ 次后爆炸。

每个玩家都想使他的仇恨值尽量大的人在最后炸弹爆炸时收到炸弹。

假设所有玩家都是绝顶聪明的，请问谁将在最后收到炸弹？

输入格式

第一行输入两个整数 $n,t$ ，表示人数和炸弹参数。

接下来 $n$ 行每行 $n$ 个数 ，其中第 $i$ 行第 $j$ 列的数表示 $a_{i,j}$ 。

接下来 $n$ 行，第 $i$ 行开头一个整数 $m_i$ ，表示 $i$ 的下家个数。紧接着 $m_i$ 个互不相同且不等于 $i$ 的整数表示 $i$ 的所有下家。

输出格式

一个整数，表示最后收到炸弹的人。

样例 #1

样例输入 #1

4 2
1 2 3 4
2 1 4 3
2 1 3 4
2 4 3 1
2 2 4
3 1 3 4
3 1 2 4
3 1 2 3

样例输出 #1

3

提示

说明/提示

【样例 #1 解释】

首先，炸弹将在两次传递后爆炸。

如果 $1$ 号第一次传递给 $2$ 号，那么 $2$ 号再传递给 $3$ 号后炸弹爆炸。

如果 $1$ 号第一次传递给 $4$ 号，那么 $4$ 号再传递给 $2$ 号后炸弹爆炸。

由于 $1$ 号对 $3$ 号的仇恨值更大，因此他会首先传给 $2$ 号，并使得最终炸弹落到 $3$ 号手上。

注意，虽然假如首先传递给 $3$ 号后会再到 $4$ 号手上，但由于 $3$ 不是 $1$ 的下家，所以这是不合法的。

数据范围

对于 $20%$ 的数据，满足 $n=2$ 。

对于另外 $40%$ 的数据，满足 $n\leq 5,t\leq 5$ 。

对于 $100%$ 的数据，满足 $n\le 1000, 所有m_i之和\le 5000,1\le t\le 5000,m_i\ge 1$ 。

#include<bits/stdc++.h>
using namespace std;
int main(){
    return 0;
} 

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

问题分析

这个问题是一个典型的图论问题，具体来说是在有向图中寻找一个特定节点的问题。在这个场景中，我们有一个由 $n$ 个节点组成的有向图，每个节点代表一个人，节点之间的边代表仇恨值，并且有一个炸弹会在传递 $t$ 次后爆炸。

我们需要找到在第 $t$ 次传递后，炸弹将会在哪个节点爆炸。由于每个节点都会尝试将炸弹传递给仇恨值最大的下家，我们可以通过模拟这个过程来找到最终的节点。

解决方案

1. 读取输入：首先，我们需要读取输入数据，包括人数 $n$，炸弹参数 $t$，仇恨矩阵 $a$，以及每个人的下家列表。

2. 构建图：使用邻接表来表示图，这样可以快速访问每个节点的下家。

3. 模拟传递过程：从节点 1 开始，每次根据当前节点的仇恨值和下家列表，选择仇恨值最大的下家进行传递。重复这个过程直到达到传递次数 $t$。

4. 输出结果：在第 $t$ 次传递后，输出当前节点的编号。

示例输入和输出

假设我们有以下输入：

3 3
1 2 3
3 2 1
1 3 2
1 2 3

这里，$n=3$，$t=3$。仇恨矩阵如下：

1 -> 2
2 -> 3
3 -> 1

下家列表如下：

1: 2
2: 3
3: 1

模拟传递过程：

• 初始节点是 1，传递给仇恨值最大的下家 2。
• 第二次传递，节点 2 传递给仇恨值最大的下家 3。
• 第三次传递，节点 3 传递给仇恨值最大的下家 1。

最终输出是节点 1。

代码实现

以下是根据上述分析实现的 C++ 代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, t;
    cin >> n >> t;

    vector<vector<int>> hate(n, vector<int>(n));
    vector<vector<int>> children(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> hate[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        for (int j = 0; j < m; ++j) {
            int c;
            cin >> c;
            children[i].push_back(c - 1); // 减1是因为输入从1开始计数
        }
    }

    int current = 0; // 炸弹初始在编号为1的玩家手中
    for (int step = 0; step < t; ++step) {
        int maxHatred = -1;
        int next = -1;
        for (int child : children[current]) {
            if (hate[current][child] > maxHatred) {
                maxHatred = hate[current][child];
                next = child;
            }
        }
        current = next;
    }

    cout << current + 1; // 输出时加1，因为数组索引从0开始，而题目编号从1开始
    return 0;
}

注意事项

• 代码中使用了 vector 来存储图的数据，这在 C++ 中是常见的做法。
• 仇恨矩阵 hate 是一个二维数组，用于存储每个节点对其他节点的仇恨值。
• 在 main 函数中，我们首先读取仇恨矩阵和下家列表，然后模拟传递过程，最后输出结果。
• 请注意，输入和输出的节点编号需要根据实际的数组索引进行调整。

这个解决方案假设所有玩家都是理性的，并且会按照题目描述的策略来传递炸弹。在实际编程中，可能还需要考虑输入验证和错误处理等问题。