以下是结果全部正确的代码（就是有点超时pwp）

666

题目描述 Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是Bessie站出来策划脱逃的时候了！这一房屋包含 � � NK 个排列成 � × � N×K 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。 Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。 但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。 由于这个数字可能非常大，只需输出该数对 1 0 9 + 7 10 9 +7 取模后的结果。 输入格式 输入的第一行包含两个空格分隔的整数 � N 和 � K （ 2 ≤ � ≤ 30000 , 2 ≤ � ≤ 6 2≤N≤30000,2≤K≤6 ）。 以下 N 行每行包含 − 1 K−1 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。 以下 K 行每行包含 − 1 N−1 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。 所有的花费均在 1 1 到 1 0 9 10 9 之间。 输出格式 一个整数：最小花费的逃脱方案的数量，对 1 0 9 + 7 10 9 +7 取模。 输入输出样例 输入 #1 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 输出 #1 10 说明/提示 这个测试样例描述了一个4x3的方阵， +-----+-----+ | | | 1 | |2 | 1 | 5 | 6 | +-----+-----+ | | | 1 | |3 | 1 | 7 | 8 | +-----+-----+ | | | 1 | |4 | 1 | | | +-----+-----+ 1 1

ChatGPD的答案都没有通过

我在CLion上测的都对的，但是时间超时了2ms,他就显示我错了

CP004171.复合逃逸--铂金 NOI/NOI+/CTSC 美国陆**程公司 通过率：0% 加入题单 题目描述 贝茜和朋友们被抓获，被困在远离农场的**大院 里，由贝茜来计划逃跑！ 该化合物包括 � � NK保持细胞排列在一个 � × � N×K 矩形网格，其中水平和垂直 相邻的单元格之间有门。每个牢房只养一头奶牛。 Bessie已经入侵了系统，并且能够解锁任何 门的子集，但每个门都有成本。为了让奶牛逃脱，贝西必须打开 足够的大门，让所有的奶牛都可以聚集在一个牢房里（这样它们就有足够的 奶牛力量来隧道到地表！贝西希望最大限度地降低 总解锁成本。 但风险比以往任何时候都高，贝西不能只 满足于一个逃跑计划：她需要后援。帮助她计算最低成本 逃跑计划的数量;如果在其中一个计划中需要解锁某些门，而不是在另一个计划中 解锁，则两个计划被认为是不同的。 由于这个数字可能非常大，因此仅输出其余数模数 1 0 9 + 7 10 9 +7. 输入格式 第一行包含两个空格分隔的整数， � N和 � K ( 2 ≤ � ≤ 30000 , 2 ≤ � ≤ 6 2≤N≤30000，2≤K≤6). 接下来的每一个 � N行包含 � − 1 K−1空格分隔整数：在水平边缘解锁每个门的成本 。 接下来的每一个 � K行包含 � − 1 N−1空格分隔整数：在垂直边缘解锁每个门的成本 。 所有费用介于 1 1和 1 0 9 10 9 包容。 在 20% 的测试用例中，可以保证 � ≤ 500 N≤500并且所有重量 都在 1 1和 5 5包容。 在另外 20% 的测试用例中，可以保证 � ≤ 5000 N≤5000. 输出格式 单个整数：最小成本逃生计划的数量，模 1 0 9 + 7 10 9 +7. 输入输出样例 输入#1 复制 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 输出#1 复制 10 说明/提示 测试用例呈现一个 4x3 网格， 1 1 +-----+-----+ | | | 1 | |2 |1 |5 |6 | +-----+-----+ | | | 1 | |3 |1 |7 |8 | +-----+-----+ | | | 1 | |4 |1 | | | +-----+-----+ 1 1 任何最低成本逃生计划都将使用成本 2 的门口、成本 3 的门口和成本 1 的 大约 1 个门口。有十种选择 不使用成本-10 边缘，所以答案是 <>。

这是什莫玩意儿

这是关于牛贝西和她的朋友被困在一个秘密基地中，需要通过打开大门帮助所有牛聚集在一个单元格以实施逃跑计划的题目。题目要求找到最小成本的逃跑计划数量，并输出其对109+710^9 + 7109+7取模后的结果。 输入包括两个整数NNN和KKK，表示矩形网格的行数和列数。接下来的NNN行每行包含K−1K-1K−1个整数，表示每个水平边的开锁成本。再接下来的KKK行每行包含N−1N-1N−1个整数，表示每个垂直边的开锁成本。 输出为一个整数，表示最小成本逃跑计划的数量，对109+710^9 + 7109+7取模后的结果。 样例中给出了一个4x3的网格，其中数字代表相邻边的开锁成本。任何最小成本逃跑计划都会使用成本为2和3的边，以及一些成本为1的边。有10种方式选择不使用成本为1的边，因此答案是10。

农场的Bessie和她的朋友们被困在一个秘密基地中，远离他们的农场。现在Bessie需要计划他们的逃跑计划！这个基地由一个N×K的矩形网格组成，网格中有NK个囚牛牢房，相邻的牢房之间有门相连。每个牢房中有一头牛。 Bessie已经成功入侵了系统，她可以解锁任意数量的门，但是每个门都有一个解锁的代价。为了让所有的牛能够聚集在一个牢房中（这样他们才能够一起挖地逃到地面上！），Bessie必须打开足够多的门。Bessie希望最小化总的解锁代价。 但是，情况比以往更加严峻，Bessie不能只满足一个逃跑计划，她需要备选方案。帮助她计算最小代价的逃跑计划的数量；如果某个门需要在一个逃跑计划中解锁但在另一个计划中不需要解锁，则认为这两个计划是不同的计划。 由于这个数量可能非常大，只需要输出它除以109+7的余数。 输入格式： 第一行包含两个以空格分隔的整数N和K（2≤N≤30000，2≤K≤6）。 接下来的N行，每行包含K-1个以空格分隔的整数，表示水平边上每个门的解锁代价。 接下来的K行，每行包含N-1个以空格分隔的整数，表示垂直边上每个门的解锁代价。 所有的代价都在1到109之间，包括1和109。 在20%的测试案例中，保证N≤500且所有权值在1到55之间。 在另外20%的测试案例中，保证N≤5000。 输出格式： 一个整数，表示最小代价逃跑计划的数量，除以109+7的余数。 输入输出样例： 输入#1 复制 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 输出#1 复制 10 说明/提示： 测试案例给出了一个4x3的网格： 1 1 +-----+-----+ | | | 1 1 2 1 | 5 | 6 | +-----+-----+ | | | 1 1 3 1 | 7 | 8 | +-----+-----+ | | | 1 1 4 1 | | | +-----+-----+ 最小代价的逃跑计划将使用代价为2的门，代价为3的门，以及一些9个代价为1的门。有10种选择不使用代价为1的门，所以答案是10。

贝西和朋友们被抓获，并被困在远离农场的一个秘密大院里，贝西必须计划他们的逃跑！该院落由 N K NK 个保持单元组成，排列成 N × K N×K 矩形网格，水平和垂直相邻单元之间有门。每个牢房恰好容纳一头牛。 贝西已经侵入了系统，并且能够解锁任何门的子集，但每个门都有成本。为了让奶牛逃脱，贝西必须打开足够多的门，让所有奶牛都可以聚集在一个牢房中（这样它们就有足够的奶牛力量来挖掘地表！）。Bessie 希望最小化总解锁成本。 但赌注比以往任何时候都更高，贝西不能满足于只有一个逃跑计划：她需要后援。帮她数数最低成本的逃跑计划有多少种；如果其中一个计划中的某些门需要解锁，而另一个计划中不需要解锁，则两个计划被视为不同。 由于这个数字可能非常大，因此仅输出其模 10 9 + 7 109+7的余数。 输入格式（文件 Escape.In）： 第一行包含两个空格分隔的整数 N N 和 K K ( 2 ≤ N ≤ 30000 , 2 ≤ K ≤ 6 2≤N≤30000,2≤K≤6 )。接下来的 N N 行中的每一行都包含 K − 1 K−1 个 空格分隔的整数：解锁水平边缘上每个门的成本。 接下来的K K行中的每一行都 包含 N − 1 N−1 个 空格分隔的整数：解锁垂直边缘上每个门的成本。 所有费用均在 1 1 至 10 9 109之间 （含）。 在20%的测试用例中，保证 N ≤ 500 N≤500 ，并且所有权重在 1 1 和 5 5之间 （包括1 1 和5 5）。 在另外 20% 的测试用例中，保证 N ≤ 5000 N≤5000。 输出格式（文件 Escape.Out）： 单个整数：最小成本逃生计划的数量，模 10 9 + 7 109+7。 样本输入： 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 样本输出： 10 测试用例呈现一个 4x3 网格， +-----+-----+ | | | 1 | |2 | 1 | 5 | 6 | +-----+-----+ | | | 1 | |3 | 1 | 7 | 8 | +-----+-----+ | | | 1 | |4 | 1 | | | +-----+-----+ 1 1 任何最小成本逃生计划都会使用成本 2 的门口、成本 3 的门口以及成本 1 的大约 9 个门口。对于不使用成本 1 的边有 10 个选择，因此答案是 10。

老师teach我的

CP004171.复合逃逸--铂金 NOI/NOI+/CTSC USACO 通过率：0% 加入题单 题目描述 贝茜和朋友们被抓获，被困在远离农场的秘密大院 里，由贝茜来计划逃跑！ 该化合物包括 � � NK保持细胞排列在一个 � × � N×K 矩形网格，其中水平和垂直 相邻的单元格之间有门。每个牢房只养一头奶牛。 Bessie已经入侵了系统，并且能够解锁任何 门的子集，但每个门都有成本。为了让奶牛逃脱，贝西必须打开 足够的大门，让所有的奶牛都可以聚集在一个牢房里（这样它们就有足够的 奶牛力量来隧道到地表！贝西希望最大限度地降低 总解锁成本。 但风险比以往任何时候都高，贝西不能只 满足于一个逃跑计划：她需要后援。帮助她计算最低成本 逃跑计划的数量;如果在其中一个计划中需要解锁某些门，而不是在另一个计划中 解锁，则两个计划被认为是不同的。 由于这个数字可能非常大，因此仅输出其余数模数 1 0 9 + 7 10 9 +7. 输入格式 第一行包含两个空格分隔的整数， � N和 � K ( 2 ≤ � ≤ 30000 , 2 ≤ � ≤ 6 2≤N≤30000，2≤K≤6). 接下来的每一个 � N行包含 � − 1 K−1空格分隔整数：在水平边缘解锁每个门的成本 。 接下来的每一个 � K行包含 � − 1 N−1空格分隔整数：在垂直边缘解锁每个门的成本 。 所有费用介于 1 1和 1 0 9 10 9 包容。 在 20% 的测试用例中，可以保证 � ≤ 500 N≤500并且所有重量 都在 1 1和 5 5包容。 在另外 20% 的测试用例中，可以保证 � ≤ 5000 N≤5000. 输出格式 单个整数：最小成本逃生计划的数量，模 1 0 9 + 7 10 9 +7. 输入输出样例 输入#1 复制 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 输出#1 复制 10 说明/提示 测试用例呈现一个 4x3 网格， 1 1 +-----+-----+ | | | 1 | |2 |1 |5 |6 | +-----+-----+ | | | 1 | |3 |1 |7 |8 | +-----+-----+ | | | 1 | |4 |1 | | | +-----+-----+ 1 1 任何最低成本逃生计划都将使用成本 2 的门口、成本 3 的门口和成本 1 的 大约 1 个门口。有十种选择 不使用成本-10 边缘，所以答案是 <>。

#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; const int MOD = 1e9 + 7; struct Edge { int u, v, weight; bool operator<(const Edge &other) const { return weight < other.weight; } }; struct UnionFind { vector<int> parent; UnionFind(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); } int find(int x) { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x]; } void unite(int x, int y) { parent[find(x)] = find(y); } }; int main() { int N, K; cin >> N >> K; vector<Edge> edges; int edgeCount = (N - 1) * K + (K - 1) * N; edges.reserve(edgeCount); }

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 1e9 + 7; struct Edge { int u, v, cost; Edge(int _u, int _v, int _cost) : u(_u), v(_v), cost(_cost) {} }; bool comp(const Edge& a, const Edge& b) { return a.cost < b.cost; } class UnionFind { public: vector<int> parent, rank; UnionFind(int size) : parent(size), rank(size, 0) { for (int i = 0; i < size; ++i) parent[i] = i; } }; // 这个函数用于构建最小生成树并返回总成本，但不计算不同的最小成本逃脱计划数量 int kruskal(vector<Edge>& edges, int N) { sort(edges.begin(), edges.end(), comp); UnionFind uf(N); int cost = 0; } int main() { // 假设N和K以及每个门的成本已经给定 int N = 5; // 行数 int K = 5; // 列数 vector<Edge> edges; }

A787型Compound Escape--铂金 NOI/NOI+/CTSC USACO 通过率：0% 加入题单 题目描述 贝茜和朋友们被抓获，被困在远离农场的一个秘密大院 里，贝茜要计划他们的逃跑！ 该化合物包括 � � NK收容单元排列成 � × � N×K 矩形网格，其中水平和垂直 相邻的单元格之间有门。每个牢房只饲养一头奶牛。 贝茜已经入侵了这个系统，并能够解锁 任何门的子集，但每个门都有成本。为了让奶牛逃脱，贝茜必须打开 足够多的大门，让所有的奶牛都可以聚集在一个牢房里（这样它们就有足够的 奶牛力量通过隧道到达地面！Bessie 希望将 总解锁成本降至最低。 但风险比以往任何时候都高，贝茜不能只满足 于一个逃跑计划：她需要后备力量。帮她计算最低成本 逃生计划的数量;如果其中一个计划中需要 解锁某个门，而另一个计划中不需要解锁，则两个计划被认为是不同的。 由于这个数字可能非常大，因此仅输出其剩余模数 1 0 9 + 7 10 9 +7. 输入格式 第一行包含两个空格分隔的整数， � N和 � K ( 2 ≤ � ≤ 30000 , 2 ≤ � ≤ 6 2≤不≤30000,2≤K≤6). 接下来的每一个 � N行包含 � − 1 K−1空格分隔整数：在水平边上解锁每个门的成本 。 接下来的每一个 � K行包含 � − 1 N−1空格分隔整数：在垂直边上解锁每个门的成本 。 所有费用介于 1 1和 1 0 9 10 9 包容。 在 20% 的测试用例中，可以保证 � ≤ 500 不≤500并且所有权重 都在 1 1和 5 5包容。 在另外 20% 的测试用例中，可以保证 � ≤ 5000 不≤5000. 输出格式 单个整数：最小成本逃逸计划的数量，模 1 0 9 + 7 10 9 +7. 输入输出样例 输入#1 复制 4 3 1 1 5 6 7 8 1 1 1 1 1 2 3 4 1 1 1 输出#1 复制 10 说明/提示 测试用例提供了一个 4x3 网格， 1 1 +-----+-----+ | | | 1 | |2 |1 |5 |6 | +-----+-----+ | | | 1 | |3 |1 |7 |8 | +-----+-----+ | | | 1 | |4 |1 | | | +-----+-----+ 1 1 任何最低成本逃生计划都将使用成本 2 的门口、成本 3 的门口和 成本 1 的大约 9 个门口。有十个选项 不使用成本 1 边缘，所以答案是 10。

以下为正文： #include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; const int MOD = 1e9 + 7; struct Edge { int u, v, weight; bool operator<(const Edge &other) const { return weight < other.weight; } }; struct UnionFind { vector<int> parent; UnionFind(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); } int find(int x) { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x]; } void unite(int x, int y) { parent[find(x)] = find(y); } }; int main() { int N, K; cin >> N >> K; vector<Edge> edges; int edgeCount = (N - 1) * K + (K - 1) * N; edges.reserve(edgeCount); } 好像有点超时了 最后是46.72MB