题意
\(A\), \(B\) 两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。
\(A\) 希望游戏进行的轮数多，\(B\) 希望游戏进行的轮数少。
对于每个 \(s = 1, 2, ..., n\) 作为起点，若双方都采用最优策略，游戏会进行多少轮。
Sol
考虑将所有边按照从大到小的顺序排序。
每次操作在当前的图上添加一条边：\(u \to v\)，因为已经排序，所以当前 \(u \to v \to \forall k \leq n\) 都是合法的情况。
我们记 \(f_{i, 0/1}\) 表示从当前点出发当前操作的人为 \(0/1\) 的游戏轮数。
所以我们只需要 \(u \to v\) 转移一次，\(v \to u\) 转移一次即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 2e5 + 5, inf = 0x7f7f7f7f;
array <tuple <int, int, int>, N> isl;
array <array <int, 2>, N> f;
/*
0 Alice
1 Bob
*/
int main() {
#ifdef ONLINE_JUDGE
freopen("increase.in", "r", stdin);
freopen("increase.out", "w", stdout);
#endif
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
get <1>(isl[i]) = read(), get <2>(isl[i]) = read();
get <0>(isl[i]) = read();
}
sort(isl.begin() + 1, isl.begin() + 1 + m, greater <tuple <int, int, int> >());
for (int i = 1; i <= n; i++)
f[i][1] = 0x7f7f7f7f;
for (int i = 1; i <= m; i++) {
int u = get <1>(isl[i]), v = get <2>(isl[i]);
int pu = f[u][0], ku = (f[u][1] == inf ? 0 : f[u][1]),
pv = f[v][0], kv = (f[v][1] == inf ? 0 : f[v][1]);
f[u][0] = max(f[u][0], kv + 1), f[u][1] = min(f[u][1], pv + 1);
f[v][0] = max(f[v][0], ku + 1), f[v][1] = min(f[v][1], pu + 1);
/* write(f[u][0]), putchar(32); */
/* write(f[u][1]), putchar(32); */
/* write(f[v][0]), putchar(32); */
/* write(f[v][1]), puts(""); */
}
for (int i = 1; i <= n; i++)
write(f[i][0]), putchar(32);
puts("");
return 0;
}