Description
有一批人质关在一个n*m的“网格”监狱中,每个网格中关押着一名人质,每个格子四面都是混凝土墙壁,作为超级英雄的你要去解救这批人质,已知破坏每一堵墙的花费,求解救所有人质的最小花费。
Input
T组数据,第一行一个数字T,第二行两个数 n,m(n,m<=500),然后有一个(n+1)*m的矩阵,表示的是整个监狱的所有横向的墙需要的花费,然后是一个n*(m+1)矩阵,表示整个监狱的所有纵向的墙的花费,矩阵里的数字都小于100且都是整数。
Output
对于每一个样例,输出 最小花费。
Sample Input
1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output
6
Hint
Source
解析:
1
2 3
2 2 2
1 1 1
2 2 2
2 1 1 2
2 1 1 2
2 3
2 2 2
3 1 3
2 2 2
2 4 1 2
2 1 2 2
2 3
2 2 2
3 6 3
2 2 2
2 4 1 2
2 2 2 2
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
using namespace std;
typedef long long LL;
const int N = 5e2 + 5,M=1e6+1000;
int n, m;
int arr[2][N][N], idx[N][N];
struct e {
int a, b, c;
}e[3 * N * N];
LL fa[M];
int cmp(const struct e& a, const struct e& b) {
return a.c < b.c;
}
int find(int a) {
if (fa[a] == a)return a;
return fa[a] = find(fa[a]);
}
int main() {
for (int i = 0, t = 0; i <= N - 2; i++) {
for (int j = 0; j <= N - 2; j++, t++) {
idx[i][j] = t;
}
}
int T;
cin >> T;
while (T--) {
int cnt = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &arr[0][i][j]);
if (i == 0) {
e[++cnt] = { 0,idx[i + 1][j],arr[0][i][j] };
}
else if (i == n) {
e[++cnt] = { 0,idx[i][j],arr[0][i][j] };
}
else {
e[++cnt] = { idx[i][j],idx[i + 1][j],arr[0][i][j]};
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
scanf("%d", &arr[1][i][j]);
if (j == 0) {
e[++cnt] = { 0,idx[i][j+1],arr[1][i][j] };
}
else if (j == m) {
e[++cnt] = { 0,idx[i][j],arr[1][i][j] };
}
else {
e[++cnt] = { idx[i][j],idx[i][j + 1],arr[1][i][j]};
}
}
}
sort(e + 1, e + 1 + cnt, cmp);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++)
fa[idx[i][j]] = idx[i][j];
}
LL ans = 0;
for (int i = 1; i <= cnt; i++) {
int a = find(e[i].a), b = find(e[i].b);
LL w = e[i].c;
if (a != b) {
ans += w;
fa[a] = b;
}
}
cout << ans << endl;
}
return 0;
}
原文地址:https://blog.csdn.net/Landing_on_Mars/article/details/134787451
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_43228.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。