Contest (nefu.edu.cn)

Description

有一批人质关在一个n*m的“网格”监狱中,每个网格中关押着一名人质每个格子四面都是混凝土墙壁,作为超级英雄的你要去解救这批人质,已知破坏每一堵墙的花费求解救所有人质最小花费

Input

T组数据,第一行个数字T,第二行两个数 nmn,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&gt;
#include<algorithm&gt;
#include<utility&gt;
#include<stack&gt;
#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&amp; a, const struct e&amp; 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", &amp;n, &amp;m);
		for (int i = 0; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf("%d", &amp;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", &amp;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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注