P2266 爱的供养题解

题目大意

给你一个矩阵 $ w $，大小为 $ n \times m $，然后你每次都从一个宝藏点开始去走旁边 $ T - 1 $ 个点施法，施法过的点就不用再走了，施法不需要耗费体力但是每一次从一个点走到另一个点需要耗费的权值为这两个点的高度差，你每次可以走的方向是上下左右。求最小需要耗费的体力。

思路

首先我们要明白一个东西就是周的定义：对于一个点 $ a $ 它可以走一步走到点 $ b $ 那么 $ b $ 就在 $ a $ 的周围，对于点 $ b $ 他可以走一步走到点 $ c $ 且 $ c \neq a $ 那么 $ c $ 在 $ b $ 的周围 $ c $ 也在 $ a $ 的周围但是要使 $ c $ 在 $ a $ 的周围必须走过 $ c $ 周围的点。

在长久的思考过后我觉得我们可以把用最小生成树 Kruskal 算法来解决这一道题，因为题目要求求与这个点连接 $ T - 1 $ 条边需要的最小体力，边得权值就设为点 $ u $ 到点 $ v $ 需要耗费的体力就行了。

对于联通块的维护我们可以用到并查集，合并并查集时如果它们的边数 $ \ge T - 1 $ 时说明他对答案可能有贡献所以我们就判断。在加体力的时候我们用当前边的权值乘上当前联通块的宝藏数量就行了当然当前联通块的边的数量需要 $ \le T - 1 $，我们的思路就完事了，代码量中偏短所以建议自己先写一下。

Code：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#define sc(ppt) scanf("%lld" , &ppt)
#define ll long long
#define int long long
#define prt printf
using namespace std;

const int maxm = 8e5 + 1 , maxn = 6e2 + 1;
const int dx[] = {0 , 0 , 0 , 1 , -1};
const int dy[] = {0 , 1 , -1 , 0 , 0};
int n , m , T , a[maxn][maxn] , vis[maxn][maxn] , oe[maxn * maxn] , anc[maxn * maxn] , Size[maxn * maxn] , sign;
int h[maxn] , cnt = 0 ;
struct edge{
	int next , to , val;
}e[maxm << 1]; // 前向心 

inline void add(int u , int v , int w){
	++ cnt;
	e[cnt].next = u ; e[cnt].to = v; e[cnt].val = w;
//	h[u] = cnt;
}

bool cmp(const edge &x , const edge &y){
	return x.val < y.val;
} // 找最小权值的边 

int get_father(int u){ // 并查集 
	if(anc[u] == u) return u;
	else return anc[u] = get_father(anc[u]); // 记忆化 
}

void Kruskal(){
	int res = 0;
	for(int i=1 ; i<=cnt ; i++){
		int u = e[i].next , v = e[i].to;
		int t1 = get_father(u) , t2 = get_father(v);
		if(t1 != t2){
			if(Size[t1] + Size[t2] >= T){
				if(Size[t1] < T) res += e[i].val * oe[t1];
				if(Size[t2] < T) res += e[i].val * oe[t2];
			}
			if(Size[t1] > Size[t2]) swap(t1 , t2);
			anc[t1] = t2;
			Size[t2] += Size[t1];
			oe[t2] += oe[t1];
			++ sign;
			if(sign == n * m - 1){
				prt("%lld" , res);
				exit(0);
			}
		}	
	}
}

signed main(){
	sc(n) ; sc(m) ; sc(T) ;
	for(int i=1 ; i<=n * m ; i++) {anc[i] = i ; Size[i] = 1;}
	for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=m ; j++) sc(a[i][j]);
	for(int i=1 ; i<=n ; i++){
		for(int j=1 ; j<=m ; j++){
			sc(vis[i][j]);
			oe[(i - 1) * m + j] = vis[i][j];
		}
	} // 预处理宝藏位置 
	for(int x=1 ; x<=n ; x++){
		for(int y=1 ; y<=m ; y++){
			for(int i=1 ; i<=4 ; i++){
				int xx = x + dx[i] , yy = y + dy[i];
				if(xx > n || xx < 1 || yy > m || yy < 1) continue;
				add((x - 1) * m + y , (xx - 1) * m + yy , abs(a[x][y] - a[xx][yy]));
			}
		}
	}
	sort(e + 1 , e + cnt + 1 , cmp);
	Kruskal();
	return 0;
}