Reku
0%

Codeforces Round #355 (Div. 2) D

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/677/D 这题比赛的时候，我感觉是一个分层的最小曼哈顿生成树，或者是用最小曼哈顿生成树的思想，四个方向扫一扫，再用树状数组搞一搞... 然而事实上是我根本不会写最小曼哈顿生成树...于是我上网找了个模板，调了一个多小时也没调出来... 确实有人写了这个做法，有空的时候补一补吧...先mark一下... 然而这个题因为数据范围比较小，所以有一个神秘的分类讨论做法 这道题一个非常直观的做法就是，从一个颜色直接枚举转移到下一个颜色，然而这样的话，如果一个图一半颜色是1，另一半颜色是2，转移的循环就是4500045000，时间显然不够... 还有一个比较直观的做法就是从一个颜色转移到下一个颜色，做一个spfa，这道题spfa的时间复杂度大概是O(nm)？，如果颜色的数目为90000的时候，时间又不够了... 那就把这两个做法结合起来！ 如果cnt[颜色1]cnt[颜色2]<=nm的话，就直接进行转移 如果cnt[颜色1]cnt[颜色2]>nm的话，就做一个spfa 这样似乎可以数学证明，整个时间复杂度是O(nmsqrt(n*m)) 当然证明只是有人在评论区里面提了一句，我也没有看懂orz 不过这题分类的思想确实值得借鉴

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
int e[310][310]={};
int n,m,p;
vector<pair<int,int>> q[90010];
int u[310][310]={};
int d[310][310]={};
bool v[310][310]={};
int c[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			u[i][j]=2147483600;
			scanf("%d",&e[i][j]);
			q[e[i][j]].push_back(make_pair(i,j));
			if(e[i][j]==1) u[i][j]=i+j-2;
		}
	}
	for(int i=1;i<p;i++)
	{
		if(q[i].size()*q[i+1].size()<=n*m)
		{
			for(int j=0;j<q[i].size();j++)
			{
				for(int k=0;k<q[i+1].size();k++)
				{
					u[q[i+1][k].first][q[i+1][k].second]=min(u[q[i+1][k].first][q[i+1][k].second],u[q[i][j].first][q[i][j].second]+abs(q[i][j].first-q[i+1][k].first)+abs(q[i][j].second-q[i+1][k].second));
				}
			}
		}
		else
		{
			queue<pair<int,int>> o;
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=m;k++)
				{
					d[j][k]=2147483600;
				}
			}
			for(int j=0;j<q[i].size();j++)
			{
				d[q[i][j].first][q[i][j].second]=u[q[i][j].first][q[i][j].second];
				v[q[i][j].first][q[i][j].second]=1;
				o.push(q[i][j]);
			}
			while(!o.empty())
			{
				int x,y,a,b;
				x=o.front().first;
				y=o.front().second;
				o.pop();
				v[x][y]=0;
				for(int j=0;j<4;j++)
				{
					a=x+c[j][0];
					b=y+c[j][1];
					if(a>=1&&a<=n&&b>=1&&b<=m)
					{
						if(d[a][b]>d[x][y]+1)
						{
							d[a][b]=d[x][y]+1;
							if(v[a][b]==0)
							{
								v[a][b]=1;
								o.push(make_pair(a,b));
							}
						}
					}
				}
			}
			for(int j=0;j<q[i+1].size();j++)
			{
				u[q[i+1][j].first][q[i+1][j].second]=d[q[i+1][j].first][q[i+1][j].second];
				//cout<<q[i+1][j].first<<" "<<q[i+1][j].second<<" "<<u[q[i+1][j].first][q[i+1][j].second]<<endl;
			}
			
		}
	}
	int ans=2147483600;
	for(int i=0;i<q[p].size();i++)
	{
		ans=min(ans,u[q[p][i].first][q[p][i].second]);
	}
	cout<<ans;
	return 0;
}