codeforces 781D Axel and Marston in Bitland
内容
Description
A couple of friends, Axel and Marston are travelling across the country of Bitland. There are n towns in Bitland, with some pairs of towns connected by one-directional roads. Each road in Bitland is either a pedestrian road or a bike road. There can be multiple roads between any pair of towns, and may even be a road from a town to itself. However, no pair of roads shares the starting and the destination towns along with their types simultaneously.
The friends are now located in the town 1 and are planning the travel route. Axel enjoys walking, while Marston prefers biking. In order to choose a route diverse and equally interesting for both friends, they have agreed upon the following procedure for choosing the road types during the travel:
The route starts with a pedestrian route.
Suppose that a beginning of the route is written in a string s of letters P (pedestrain road) and B (biking road). Then, the string is appended to s, where stands for the string s with each character changed to opposite (that is, all pedestrian roads changed to bike roads, and vice versa).
In the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.
After that the friends start travelling from the town 1 via Bitlandian roads, choosing the next road according to the next character of their route type each time. If it is impossible to choose the next road, the friends terminate their travel and fly home instead.
Help the friends to find the longest possible route that can be travelled along roads of Bitland according to the road types choosing procedure described above. If there is such a route with more than 1018 roads in it, print -1 instead.
Input
The first line contains two integers n and m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2n2) — the number of towns and roads in Bitland respectively.
Next m lines describe the roads. i-th of these lines contains three integers vi, ui and ti (1 ≤ vi, ui ≤ n, 0 ≤ ti ≤ 1), where vi and ui denote start and destination towns indices of the i-th road, and ti decribes the type of i-th road (0 for a pedestrian road, 1 for a bike road). It is guaranteed that for each pair of distinct indices i, j such that 1 ≤ i, j ≤ m, either vi ≠ vj, or ui ≠ uj, or ti ≠ tj holds.
Output
If it is possible to find a route with length strictly greater than 1018, print -1. Otherwise, print the maximum length of a suitable path.
Examples
input
2 2
1 2 0
2 2 1
output
3
input
2 3
1 2 0
2 2 1
2 2 0
output
-1
Note
In the first sample we can obtain a route of length 3 by travelling along the road 1 from town 1 to town 2, and then following the road 2 twice from town 2 to itself.
In the second sample we can obtain an arbitrarily long route by travelling the road 1 first, and then choosing road 2 or 3 depending on the necessary type.
题解
首先考虑dp，那么可以用f[i][j][k][l]表示当前是在递推以1开头的串还是0开头的串/长度为2的几次幂/起点是k/终点是l的路径是否有可行方案。
递推的话就是如果长度为$2^{j−1}$的正串可以从x跑到某个中间点k，长度为$2^{j−1}$的反串可以从k跑到y，那么就有长度为$2^j$的合法路径从x跑到y。
如果把第四维用bitset压起来的话转移就直接做位运算就可以了。
构造答案的过程是从高位到低位贪心地依次判断这一位能不能加进去，就是开一个bitset表示前面更高的那些位弄完了以后哪些点是可行的终点，一开始只有1号点一个点是可行的。然后每一位的时候枚举所有的点，如果这个点是可行的终点说明这个点后面还能接上一段路。最后如果这一位存在可行方案就把这一位加进去。
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
bitset <510> f[2][63][510], g, temp;
long long ans, ton[63];
int n, m, x, y, z, now;
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &x, &y, &z),
f[z][0][x][y] = 1;
for (int i = 1; i <= 60; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) {
if (f[0][i - 1][j][k] != 0)
f[0][i][j] |= f[1][i - 1][k];
if (f[1][i - 1][j][k] != 0)
f[1][i][j] |= f[0][i - 1][k];
}
if (f[0][61][1].count()) {
puts("-1");
return 0;
}
temp[1] = 1, ton[0] = 1;
for (int i = 1; i <= 60; ++i)
ton[i] = ton[i - 1] * 2;
for (int i = 60; i >= 0; --i) {
g.reset();
for (int j = 1; j <= n; ++j)
if (temp[j])
g |= f[now][i][j];
if (g.count())
now ^= 1, temp = g, ans |= ton[i];
}
if (ans > 1e18)
puts("-1");
else
printf("%lld\n", ans);
}