【NOIP提高组】 关押罪犯
- C语言
- C++语言实现
- Python语言实现
|
💐The Begin💐点点关注，收藏不迷路💐
|
S城现有两座监狱，一共关押着N名罪犯，编号分别为1-N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入
输入的每行中两个数之间用一个空格隔开。第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。
数据保证1<aj=<=bj<=N ，0 < cj≤ 1,000,000,000，且每对罪犯组合只出现一次。
输出
输出共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
样例输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出
3512
提示
【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。
【数据范围】对于30%的数据有N≤ 15。对于70%的数据有N≤ 2000，M≤ 50000。对于100%的数据有N≤ 20000，M≤ 100000。
C语言
#include <stdio.h>
#include <stdlib.h>
// 定义最大节点数和最大边数
#define MAX_N 20005
#define MAX_M 100005
// 结构体表示边的信息，包含两个端点和边的权重（怨气值）
typedef struct {
int a;
int b;
int c;
} Edge;
// 比较函数，用于qsort按照边的权重（怨气值）从大到小排序
int compare(const void *p1, const void *p2) {
const Edge *edge1 = (const Edge *)p1;
const Edge *edge2 = (const Edge *)p2;
return edge2->c - edge1->c;
}
// 查找并返回节点x所在集合的代表元素（根）
int find(int x, int fa[]) {
if (fa[x] == x) {
return x;
} else {
return fa[x] = find(fa[x], fa);
}
}
// 读取一个整数
int read() {
int x = 0;
int f = 1;
char ch = getchar();
// 跳过非数字字符，处理正负号
while (ch < '0' || ch > '9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
// 读取数字字符并转换为整数
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * f;
}
int main() {
int n; // 罪犯的数量
int m; // 存在仇恨的罪犯对数
Edge e[MAX_M]; // 存储边的信息数组
int fa[2 * MAX_N]; // 并查集数组，用于存储每个节点的父节点
// 读取罪犯数量和存在仇恨的罪犯对数
n = read();
m = read();
// 读取每条边的两个端点和边的权重（怨气值）
for (int i = 1; i <= m; i++) {
e[i].a = read();
e[i].b = read();
e[i].c = read();
}
// 初始化并查集数组，每个节点的父节点初始化为自身
for (int i = 1; i <= 2 * n; i++) {
fa[i] = i;
}
// 使用qsort对边按照权重（怨气值）从大到小排序
qsort(e + 1, m, sizeof(Edge), compare);
// 遍历排序后的边，尝试将罪犯分配到不同集合（监狱）
for (int i = 1; i <= m; i++) {
int x = find(e[i].a, fa);
int y = find(e[i].b, fa);
if (x == y) {
// 如果两个端点所在集合相同，说明会发生冲突，输出当前边的权重（最小冲突影响力）
printf("%d", e[i].c);
return 0;
}
// 将两个端点所在集合分别与对方集合的补集合并
fa[y] = find(e[i].a + n, fa);
fa[x] = find(e[i].b + n, fa);
}
// 如果所有边都处理完没有发现冲突，输出0
printf("0");
return 0;
}
C++语言实现
#include <iostream>
#include <algorithm>
// 定义最大节点数和最大边数
const int MAX_N = 20005;
const int MAX_M = 100005;
// 结构体表示边的信息，包含两个端点和边的权重（怨气值）
struct Edge {
int a;
int b;
int c;
};
// 比较函数，用于按照边的权重（怨气值）从大到小排序
bool cmp(const Edge& p1, const Edge& p2) {
return p1.c > p2.c;
}
// 查找并返回节点x所在集合的代表元素（根）
int find(int x, int fa[]) {
if (fa[x] == x) {
return x;
} else {
return fa[x] = find(fa[x], fa);
}
}
int main() {
int n; // 罪犯的数量
int m; // 存在仇恨的罪犯对数
Edge e[MAX_M]; // 存储边的信息数组
int fa[2 * MAX_N]; // 并查集数组，用于存储每个节点的父节点
// 读取罪犯数量和存在仇恨的罪犯对数
std::cin >> n;
std::cin >> m;
// 读取每条边的两个端点和边的权重（怨气值）
for (int i = 1; i <= m; i++) {
std::cin >> e[i].a;
std::cin >> e[i].b;
std::cin >> e[i].c;
}
// 初始化并查集数组，每个节点的父节点初始化为自身
for (int i = 1; i <= 2 * n; i++) {
fa[i] = i;
}
// 对边按照权重（怨气值）从大到小排序
std::sort(e + 1, e + m + 1, cmp);
// 遍历排序后的边，尝试将罪犯分配到不同集合（监狱）
for (int i = 1; i <= m; i++) {
int x = find(e[i].a, fa);
int y = find(e[i].b, fa);
if (x == y) {
// 如果两个端点所在集合相同，说明会发生冲突，输出当前边的权重（最小冲突影响力）
std::cout << e[i].c << std::endl;
return 0;
}
// 将两个端点所在集合分别与对方集合的补集合并
fa[y] = find(e[i].a + n, fa);
fa[x] = find(e[i].b + n, fa);
}
// 如果所有边都处理完没有发现冲突，输出0
std::cout << "0" << std::endl;
return 0;
}
Python语言实现
MAX_N = 20005
MAX_M = 100005
def find(x, fa):
if fa[x] == x:
return x
return find(fa[x], fa)
n, m = map(int, input().split()) # 读取罪犯数量和存在仇恨的罪犯对数
e = [] # 存储边的信息列表
# 读取每条边的两个端点和边的权重（怨气值）
for _ in range(m):
a, b, c = map(int, input().split())
e.append((a, b, c))
fa = list(range(2 * MAX_N)) # 初始化并查集列表，每个节点的父节点初始化为自身
# 对边按照权重（怨气值）从大到小排序
e.sort(key=lambda x: x[2], reverse=True)
# 遍历排序后的边，尝试将罪犯分配到不同集合（监狱）
for i in range(m):
x = find(e[i][0], fa)
y = find(e[i][1], fa)
if x == y:
# 如果两个端点所在集合相同，说明会发生冲突，输出当前边的权重（最小冲突影响力）
print(e[i][2])
break
# 将两个端点所在集合分别与对方集合的补集合并
fa[y] = find(e[i][0] + MAX_N, fa)
fa[x] = find(e[i][1] + MAX_N, fa)
else:
# 如果所有边都处理完没有发现冲突，输出0
print("0")
|
💐The End💐点点关注，收藏不迷路💐
|
