NKOJ 2770 难度系数（最小生成树）

发表于 |
字数统计: 1,014字 | 阅读时长 ≈ 5min

P2770【USACO 2014 January Gold】难度系数

问题描述

奶牛冬奥会的越野滑雪场可以被看做是一个M x N(1 <= M,N <= 500)的网格区域。其中每格都有一个海拔高度（海拔高度的范围：0 .. 1,000,000,000）。

其中一些格子被设计成了滑雪的起点，赛会组织者想要给每个滑雪起点做一个难度的评级。
一个起点P的难度系数D应该尽可能小，使得一只奶牛能够成功的滑过至少T(1 <= T <= MN)个格子。如果奶牛从P出发，它只能朝相邻的格子滑行，且要求相邻的格子的海拔高度差的绝对值不超过D。

请帮助组织者计算出每个起点的难度系数。

输入格式

第一行，三个整数M, N, 和 T
接下来是一个M x N的整数矩阵，表示每个格子的海拔高度
接下来是一个M x N的矩阵，矩阵由数字0和1构成，数字1表示该处是一个起点。

输出格式

一个整数，表示所有起点的难度系数总和(可能超过int范围)

样例输入

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

样例输出

24

首先我们要理解一个起点的难度系数是指：从该起点出发经过的相邻的两点的高度差的最大值。
同时我们注意到每个点是可以反复经过的，并且反复经过不会影响难度系数。
因此我们可以发现，对于一个起点，它最后经过的所有的点必然是一个联通块。我们定义两点之间的边的权值等于他们的高度差。那么一个起点的难度系数就是它所在联通块中最大的边权。

我们考虑将所有的边按照权值从小到大排序，将Kruscal算法修改一下。
每次选出权值最小的边，合并它连接的两个联通块，如果合并后的大联通块包含的点数大于等于T，并且小联通块各自包含的点数小于T，那么ans+=小联通块中起点数*当前边的权值。

正确性是显然的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define Abs(a,b) ((a>b)?(a-b):(b-a))
#define N 505
#define M 500005
using namespace std;
struct node{int x,y,z;}edge[M];
bool cmp(node a,node b)
{return a.z<b.z;}
int m,n,t,map[N][N],Map[N][N],id[N][N],F[M],size[M],p[M],tot,TOT,cnt;
long long ans;
int GF(int v)
{
	if(F[v]!=v)F[v]=GF(F[v]);
	return F[v];
}
int main()
{
	int i,j,x,y,k;
	scanf("%d%d%d",&m,&n,&t);
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)scanf("%d",&map[i][j]);
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		scanf("%d",&Map[i][j]);
		cnt+=Map[i][j];//cnt表示起点总数
	}
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		id[i][j]=++tot;
		size[tot]=Map[i][j];//size记录起点数
	}
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		if(i!=m)
		{
			TOT++;
			edge[TOT].x=id[i][j];
			edge[TOT].y=id[i+1][j];
			edge[TOT].z=Abs(map[i][j],map[i+1][j]);
		}
		if(j!=n)
		{
			TOT++;
			edge[TOT].x=id[i][j];
			edge[TOT].y=id[i][j+1];
			edge[TOT].z=Abs(map[i][j],map[i][j+1]);
		}
	}
	sort(edge+1,edge+TOT+1,cmp);
	for(i=1;i<=tot;i++)F[i]=i,p[i]=1;//p记录总点数
	i=1;
	while(cnt&&i<=TOT)
	{
		x=GF(edge[i].x);
		y=GF(edge[i].y);
		if(x!=y)
		{
			if(p[x]+p[y]>=t)
			{
				if(p[x]<t)ans+=1ll*size[x]*edge[i].z,cnt-=size[x];
				if(p[y]<t)ans+=1ll*size[y]*edge[i].z,cnt-=size[y];
			}
			F[x]=y;
			size[y]+=size[x];
			p[y]+=p[x];
		}
		i++;
	}
	cout<<ans;
}