2016北京集训测试赛（七）Problem A: 自动机

Solution

注意到这一题并不要求字符串最短或者是字典序最小, 因此直接构造就可以了. 我们对于每个点\(u \ne 0\)找到一个串\(S\), 使得\(T(u, S) = T(0, S)\), 时间复杂度为\(O(n^3m)\). 假如我们发现对于某个点无法找到一个这样的串, 则说明无解. 接着我们用一个集合来表示自动机中所有点. 对于每个非零的点, 我们用前面求出来的串将其变成\(0\), 同时用这个串更新集合中的其他节点即可. 总时间复杂度: \(O(n^4 + n^3m)\)

#include <cstdio>

#include <cctype>

#include <cstring>

namespace Zeonfai

{

	inline int getInt()

	{

		int a = 0, sgn = 1;

		char c;

		while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

		while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

		return a * sgn;

	}

}

const int N = 100, M = 26;

int n, m;

struct automaton

{

	struct node

	{

		int edg[M], pth[N * N], len;

	}nd[N];

	inline void addEdge(int u, int c, int v)

	{

		nd[u].edg[c] = v;

	}

	int vis[N][N], flg;

	void DFS(int u, int v, int len, int S)

	{

		vis[u][v] = 1;

		if(! u && ! v)

		{

			flg = 1; nd[S].len = len;

			return;

		}

		for(int i = 0; i < m; ++ i) if(! flg && ! vis[nd[u].edg[i]][nd[v].edg[i]]) nd[S].pth[len] = i, DFS(nd[u].edg[i], nd[v].edg[i], len + 1, S);

	}

	void getAnswer()

	{

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

		{

			memset(vis, 0, sizeof(vis));

			flg = 0; nd[i].len = -1;

			DFS(0, i, 0, i);

			if(nd[i].len == -1)

			{

				puts("[impossible]");

				return;

			}

		}

		static int stt[N];

		for(int i = 0; i < n; ++ i) stt[i] = i;

		while(1)

		{

			int p = 0;

			for(; p < n; ++ p) if(stt[p]) break;

			if(p == n) break;

			for(int i = 0; i < nd[stt[p]].len; ++ i) putchar('a' + nd[stt[p]].pth[i]);

			for(int i = 0; i < n; ++ i) if(stt[i] && i ^ p) for(int j = 0; j < nd[stt[p]].len; ++ j) stt[i] = nd[stt[i]].edg[nd[stt[p]].pth[j]];

			stt[p] = 0;

		}

	}

}G;

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("automaton.in", "r", stdin);

	freopen("automaton.out", "w", stdout);

	#endif

	using namespace Zeonfai;

	n = getInt(), m = getInt();

	for(int i = 0; i < n; ++ i) for(int j = 0; j < m; ++ j) G.addEdge(i, j, getInt());

	G.getAnswer();

}