@loj - 2090@ 「ZJOI2016」旅行者

@description@
@solution@
@accepted code@
@details@

@description@

小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有 n 条从东到西的道路和 m 条从南到北的道路，这些道路两两相交形成 n*m 个路口 (i, j) (1<=i<=n, 1<=j<=m)。

她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口 (i, j) 到路口 (i, j+1) 需要时间 r(i, j)，从路口 (i, j) 到路口 (i+1, j) 需要时间 c(i, j)。注意这里的道路是双向的。

小 Y 有 q 个询问，她想知道从路口 (x1, y1) 到路口 (x2, y2) 最少需要花多少时间。

输入格式

第一行包含两个正整数 n,m，表示城市的大小。

接下来 n 行，每行包含 m-1 个整数，第 i 行第 j 个正整数表示从一个路口到另一个路口的时间 r(i,j)。

接下来 n-1 行，每行包含 m 个整数，第 i 行第 j 个正整数表示从一个路口到另一个路口的时间 c(i,j)。

接下来一行，包含一个正整数 q，表示小 Y 的询问个数。

接下来 q 行，每行包含四个正整数 x1,y1,x2,y2，表示两个路口的位置。

输出格式

输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

样例输入

2 2

2

3

6 4

2

1 1 2 2

1 2 2 1

样例输出

6

7

数据范围与提示

对于所有的测试数据，n*m <= 2*10^4，保证相邻路口之间的时间不超过 10^4，即 1<=r(i, j), c(i, j)<=10^4。

@solution@

显然不能每个点对都跑一遍最短路。

注意到在网格图中，对于两个点 (x1, y1), (x2, y2)，它们的最短路必然要跨越 x1 ~ x2 之间的行与 y1 ~ y2 之间的列。

然后我们考虑分治：

假如当前分治到的矩阵为 p*q，为了防止被卡，我们每次选取 max(p, q) 进行切割。

设切割的中线为 mid，枚举 mid 这条线上的所有点 k 求最短路。于是我们可以求得经过 mid 这条线中所有的路径中的最短路。

都在 mid 的同一边的，也需要统计经过 mid 的路径，不然会漏掉一些路径。

那么接下来就是不经过 mid 的那些路径，于是就以 mid 为界分为两部分，然后两部分分别递归下去。

如果某个询问跨越了 mid，就不把这个询问往下传了。否则就往它所在的那部分传。

复杂度？据说是 \(O(S\sqrt{S}\log S)\)（其中 S = n*m 为总点数）。

感知一下：当 \(n = m = \sqrt{S}\) 时取得最值。此时的复杂度就是如上的复杂度（log 是最短路的复杂度）。

@accepted code@

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN = 20000;

const int MAXQ = 100000;

const int INF = (1<<30);

struct edge{

	int to, dis;

	edge *nxt;

}edges[4*MAXN + 5], *adj[MAXN + 5], *ecnt = &edges[0];

void addedge(int u, int v, int w) {

	edge *p = (++ecnt);

	p->to = v, p->dis = w, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->dis = w, p->nxt = adj[v], adj[v] = p;

}

int n, m, q;

inline int id(int x, int y) {

	return (x - 1)*m + y;

}

struct query{

	int x1, y1, x2, y2, u, v, ind;

	query(int _x1=0, int _y1=0, int _x2=0, int _y2=0, int _i=0) :

		x1(_x1), y1(_y1), x2(_x2), y2(_y2), u(id(x1, y1)), v(id(x2, y2)), ind(_i) {}

}qry[MAXQ + 5];

bool tag[MAXN + 5];

int num[MAXN + 5], rev[MAXN + 5], tot;

int dis[MAXN + 5], hp[MAXN + 5], f[MAXN + 5];

void update(int x, int k) {

	f[rev[x]] = k;

	while( x ) {

		hp[x] = rev[x];

		if( (x<<1) <= tot && f[hp[x]] > f[hp[x<<1]] )

			hp[x] = hp[x<<1];

		if( (x<<1|1) <= tot && f[hp[x]] > f[hp[x<<1|1]] )

			hp[x] = hp[x<<1|1];

		x >>= 1;

	}

}

void dijkstra(int s) {

	update(num[s], dis[s] = 0);

	while( f[hp[1]] != INF ) {

		int x = hp[1];

//		printf("! %d %d\n", dis[x], x);

		update(num[x], INF);

		for(edge *p=adj[x];p;p=p->nxt) {

			if( !tag[p->to] ) continue;

			if( dis[x] + p->dis < dis[p->to] )

				update(num[p->to], dis[p->to] = dis[x] + p->dis);

		}

	}

}

int ans[MAXQ + 5];

void solve(int l, int r, int u, int d, int q) {

//	printf("! %d %d %d %d : %d\n", l, r, u, d, q);

	if( l > r || u > d || !q ) return ;

	if( r - l > d - u ) {

		int mid = (l + r) >> 1; tot = 0;

		for(int i=l;i<=r;i++)

			for(int j=u;j<=d;j++) {

				tag[id(i, j)] = true;

				num[id(i, j)] = (++tot), hp[tot] = id(i, j), rev[tot] = id(i, j);

			}

		for(int i=u;i<=d;i++) {

			for(int x=l;x<=r;x++)

				for(int y=u;y<=d;y++)

					dis[id(x, y)] = INF;

			dijkstra(id(mid, i));

			for(int j=1;j<=q;j++)

				ans[qry[j].ind] = min(ans[qry[j].ind], dis[qry[j].u] + dis[qry[j].v]);

		}

		for(int i=l;i<=r;i++)

			for(int j=u;j<=d;j++)

				tag[id(i, j)] = false;

		int p = 0;

		for(int i=1;i<=q;i++)

			if( qry[i].x1 < mid && qry[i].x2 < mid )

				swap(qry[++p], qry[i]);

		solve(l, mid - 1, u, d, p);

		int tmp = p + 1; p = 0;

		for(int i=tmp;i<=q;i++)

			if( qry[i].x1 > mid && qry[i].x2 > mid )

				swap(qry[++p], qry[i]);

		solve(mid + 1, r, u, d, p);

	}

	else {

		int mid = (u + d) >> 1; tot = 0;

		for(int i=l;i<=r;i++)

			for(int j=u;j<=d;j++) {

				tag[id(i, j)] = true;

				num[id(i, j)] = (++tot), hp[tot] = id(i, j), rev[tot] = id(i, j);

			}

		for(int i=l;i<=r;i++) {

			for(int x=l;x<=r;x++)

				for(int y=u;y<=d;y++)

					dis[id(x, y)] = INF;

			dijkstra(id(i, mid));

			for(int j=1;j<=q;j++)

				ans[qry[j].ind] = min(ans[qry[j].ind], dis[qry[j].u] + dis[qry[j].v]);

		}

		for(int i=l;i<=r;i++)

			for(int j=u;j<=d;j++)

				tag[id(i, j)] = false;

		int p = 0;

		for(int i=1;i<=q;i++)

			if( qry[i].y1 < mid && qry[i].y2 < mid )

				swap(qry[++p], qry[i]);

		solve(l, r, u, mid - 1, p);

		int tmp = p + 1; p = 0;

		for(int i=tmp;i<=q;i++)

			if( qry[i].y1 > mid && qry[i].y2 > mid )

				swap(qry[++p], qry[i]);

		solve(l, r, mid + 1, d, p);

	}

}

int main() {

	scanf("%d%d", &n, &m);

	int cnt = 0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			f[id(i, j)] = INF;

	for(int i=1;i<=n;i++)

		for(int j=1;j<m;j++) {

			int x; scanf("%d", &x);

			addedge(id(i, j), id(i, j + 1), x);

		}

	for(int i=1;i<n;i++)

		for(int j=1;j<=m;j++) {

			int x; scanf("%d", &x);

			addedge(id(i, j), id(i + 1, j), x);

		}

	scanf("%d", &q);

	for(int i=1;i<=q;i++) {

		int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		qry[i] = query(x1, y1, x2, y2, i), ans[i] = INF;

	}

	solve(1, n, 1, m, q);

	for(int i=1;i<=q;i++)

		printf("%d\n", ans[i]);

}

@details@

ZJOI 的题都是神仙题 * 1。

目前loj最慢，欢迎挑战。

我也不知道为什么我常数这么大。。。

巴特西

@loj - 2090@ 「ZJOI2016」旅行者

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章