[BZOJ1138][POI2009]Baj 最短回文路

试题描述

N个点用M条有向边连接，每条边标有一个小写字母。对于一个长度为D的顶点序列，回答每对相邻顶点Si到Si+1的最短回文路径。如果没有，输出-1。如果有，输出最短长度以及这个字符串。

输入

第一行正整数N和M ( 2 ≤ N ≤ 400 , 1 ≤ M ≤ 60,000 ) 接下来M行描述边的起点，终点，字母。接下来D表示询问序列长度 ( 2 ≤ D ≤ 100 ) 再接下来D个1到N的整数

输出

对于D-1对相邻点，按要求输出一行。如果没合法方案，输出-1。如果有合法，输出最短长度

输入示例

  a

  x

  b

  l

  y

  z

  a

输出示例

数据规模及约定

见“输入”

题解

朴素的 dp 是这样的：设 f[i][j] 表示节点 i 到节点 j 的最短回文长度，转移的时候枚举字母 x，设节点 j 沿着带有字母 x 的边走一格所能到达的点集为集合 A，设 i 逆着带有字母 x 的边走一格所能达到的点集为集合 B。那么对于 ∀a ∈ A, ∀b ∈ B，就可以更新 f[a][b] 了，即 f[a][b] = min{ f[a][b], f[i][j] + 2 }。

但是我们发现这个算法被爆菊了。。。就是如果有很多条相同字母的边指向 i，相同字母的边从 j 出发，转移就会被卡成 O(n²) 的了。。。

解决方式就是添加一个中间状态 g[i][j][c]，表示节点 i 到节点 j 的路径最后一个字母是 c，并且除掉最后一个字母后它就是一个回文路径，在这样的情况下的最短长度。那么对于状态 f[i][j]，可以用节点 j 沿着字母 c（枚举）走一格到达的所有节点 b 来更新 g[i][b][c]；对于状态 g[i][b][c]，可以用节点 i 逆着字母 c（这个字母是固定的，即状态中的字母）走一格到达的所有节点 a 来更新 f[a][b]，这样状态数变成了原来的 27 倍，转移复杂度变成了 O(n)。

转移顺序比较乱，可以用 BFS 帮助转移。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <queue>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 410

#define maxa 26

#define maxm 10660

bool G[maxn][maxn][maxa];

int f[maxn][maxn], g[maxn][maxn][maxa];

vector <int> from[maxn][maxa], to[maxn][maxa];

void AddEdge(int a, int b, int c) {

	to[a][c].push_back(b);

	from[b][c].push_back(a);

	return ;

}

struct Pair {

	int a, b, c;

	Pair() {}

	Pair(int _1, int _2, int _3): a(_1), b(_2), c(_3) {}

};

queue <Pair> Q;

int main() {

	int n = read(), m = read();

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

		int a = read(), b = read(); char ch[2]; scanf("%s", ch);

		G[a][b][ch[0]-'a'] = 1;

	}

	memset(f, -1, sizeof(f)); memset(g, -1, sizeof(g));

	for(int i = 1; i <= n; i++) Q.push(Pair(i, i, -1)), f[i][i] = 0;

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

		for(int j = 1; j <= n; j++) if(i != j) {

			bool fl = 0;

			for(int c = 0; c < maxa; c++) if(G[i][j][c]) {

				AddEdge(i, j, c);

				fl = 1; break;

			}

			if(fl) f[i][j] = 1, Q.push(Pair(i, j, -1));

		}

	while(!Q.empty()) {

		Pair u = Q.front(); Q.pop();

		int a = u.a, b = u.b, c = u.c, tmp = c < 0 ? f[a][b] : g[a][b][c];

//		printf("(%d, %d, %d)\n", a, b, c);

		if(c < 0)

			for(c = 0; c < maxa; c++)

				for(int i = 0; i < to[b][c].size(); i++) {

					int B = to[b][c][i];

					if(g[a][B][c] < 0) g[a][B][c] = tmp + 1, Q.push(Pair(a, B, c));

				}

		else

			for(int i = 0; i < from[a][c].size(); i++) {

				int A = from[a][c][i];

				if(f[A][b] < 0) f[A][b] = tmp + 1, Q.push(Pair(A, b, -1));

			}

	}

	int q = read(), st = read();

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

		int u = read();

		printf("%d\n", f[st][u]);

		st = u;

	}

	return 0;

}

巴特西

[BZOJ1138][POI2009]Baj 最短回文路

最新文章

热门文章