题面
(n)个点，(m)条边的有向图，边有边权(w)，一条路径上第(i)条边(e)的代价是(w_e cdot 10^{i - 1})，问：
- 任意一条路径的最大代价
- 代价等于最大代价的路径条数
输出一问一行，如果答案为无穷大，输出(inf)，若第一问为(inf)，第二问也为(inf)
题外话
早上洋洋洒洒打了(3.7k)结果爆零了……天知道我是怎么有信心拿(long long)存下路径代价的……然后这么个题我居然改了一下午……
不过发现(sublime text)这次更新直接支持了(fcitx)输入，不用加插件就能输中文注释了……
解析
按输出(inf)讨论：
- 两个(inf)
- 如果有正环，可以在上面无限走
- 如果零环的后继有正权边，可以无限走然后出去走正权边
- 第一问非(inf)，第二问(inf)
- 没有正环
- 有一条代价最大的路径结束位置是零环
- 有一条代价最大的路径结束位置到前一个零环之间没有正权边
- 两个非(inf)
- 没有正环
- 代价最大的路径都不经过零环
于是先缩点，判正环，然后把有正权边后继的(SCC)都标记，顺便标记零环和能走到零环的(SCC)为(inf)
重新建图，这次就只建出发点有正权边后继的边
之后拓扑排序计算到达点(i)经过的最大边数(dist_i)和所有路径经过的最大边数(maxd)（因为重建的图保证不会跑出前导零，所以边数越大越优）
反向重新建图，只保留上次的那些边中能推出(dist_u + 1 == dist_v)的边
枚举(j)从(1)到(maxd)，每次维护终点为(dist_i == maxd)的点，长度为(j)的最大路径的起点，把路径数的(inf)标记和路径数统计都收上来，同时可以得到第(maxd - j + 1)位的答案
最后把所有起点的路径数加起来就是第二问答案，如果有标记就输出(inf)
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define MAXN 100005
#define MAXM 1000005
#define REG register
typedef long long LL;
typedef std::pair<int, int> pii;
const int mod = 998244353;
void Tarjan(int);
void rebuild();
void rebuild_opp();
void dfs(int);
void Topo();
char gc();
int read();
struct Graph {
struct Edge {
int v, next, w;
Edge(int _v = 0, int _n = 0, int _w = 0):v(_v), next(_n), w(_w) {}
} edge[MAXM];
int head[MAXN], deg[MAXN], cnt;
void init() { memset(head, -1, sizeof head); memset(deg, 0, sizeof deg); cnt = 0; }
void insert(int u, int v, int w) { edge[cnt] = Edge(v, head[u], w); head[u] = cnt++; ++deg[v]; }
} G;
int N, M, U[MAXM], V[MAXM], W[MAXM];
int idx, dfn[MAXN], low[MAXN], belong[MAXN], scc_tot, stk[MAXN], top, dist[MAXN], maxd, dp[MAXN], size[MAXN];
bool vis[MAXN], in_stk[MAXN], inf[MAXN], positive[MAXN], tag[MAXN];
std::vector<int> pos, new_pos, path;
inline void inc(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline void dec(int &x, int y) { x -= y; if (x < 0) x += mod; }
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; }
inline int sub(int x, int y) { x -= y; return x < 0 ? x + mod : x; }
int main() {
freopen("tried.in", "r", stdin);
freopen("tried.out", "w", stdout);
N = read(), M = read();
G.init();
for (REG int i = 0; i < M; ++i) {
U[i] = read(), V[i] = read(), W[i] = read();
G.insert(U[i], V[i], W[i]);
}
for (REG int i = 1; i <= N; ++i)
if (!dfn[i]) Tarjan(i);
G.init();
for (REG int i = 0; i < M; ++i) {
int x = belong[U[i]], y = belong[V[i]], z = W[i];
if (x == y) { positive[x] |= (z > 0), ++size[x]; }
else G.insert(x, y, z);
}
for (REG int i = 1; i <= scc_tot; ++i) if (!vis[i]) dfs(i);
for (REG int i = 1; i <= scc_tot; ++i) if (size[i] && positive[i]) { printf("inf
inf
"); return 0; }
rebuild();
Topo();
for (int i = 1; i <= scc_tot; ++i) if (dist[i] == maxd) {
pos.push_back(i);
tag[i] = inf[i];
} else dp[i] = 0;
rebuild_opp();
memset(vis, 0, sizeof vis);
for (REG int len = 1; len <= maxd; ++len) {
int tmp = -1;
for (REG int i = 0; i < pos.size(); ++i) for (int j = G.head[pos[i]]; ~j; j = G.edge[j].next)
tmp = std::max(tmp, G.edge[j].w);
path.push_back(tmp);
for (REG int i = 0; i < pos.size(); ++i) {
int u = pos[i];
for (REG int j = G.head[u]; ~j; j = G.edge[j].next)
if (G.edge[j].w == tmp) {
int v = G.edge[j].v;
if (!vis[v]) new_pos.push_back(v), vis[v] = 1;
tag[v] |= tag[u];
inc(dp[v], dp[u]);
}
}
pos = new_pos, new_pos.clear();
}
if (!maxd) printf("0");
else for (REG int i = 0; i < maxd; ++i) printf("%d", path[i]);
puts("");
int tot = 0, flag = 0;
for (REG int i = 0; i < pos.size(); ++i) inc(tot, dp[pos[i]]), flag |= tag[pos[i]];
if (flag) puts("inf");
else printf("%d
", tot);
return 0;
}
inline char gc() {
static char buf[1000000], *p1, *p2;
if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin);
return p1 == p2 ? EOF : *p2++;
}
inline int read() {
int res = 0; char ch = gc();
while (ch < '0' || ch > '9') ch = gc();
while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + ch - '0', ch = gc();
return res;
}
void Tarjan(int u) {
in_stk[u] = 1, dfn[u] = low[u] = ++idx, stk[top++] = u;
for (int i = G.head[u]; ~i; i = G.edge[i].next) {
int v = G.edge[i].v, w = G.edge[i].w;
if (!dfn[v]) {
Tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if (in_stk[v]) low[u] = std::min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
REG int p; ++scc_tot;
do { p = stk[--top]; belong[p] = scc_tot; in_stk[p] = 0; } while (p ^ u);
}
}
void rebuild() {
G.init();
for (REG int i = 0; i < M; ++i) {
int x = belong[U[i]], y = belong[V[i]], z = W[i];
if (x == y || !positive[x]) continue;
G.insert(x, y, z);
}
}
void rebuild_opp() {
G.init();
for (REG int i = 0; i < M; ++i) {
int x = belong[U[i]], y = belong[V[i]], z = W[i];
if (x == y || !positive[x] || dist[x] + 1 != dist[y]) continue;
G.insert(y, x, z);
}
}
void Topo() {
int que[MAXN], hd = 0, tl = 0;
for (REG int i = 1; i <= scc_tot; ++i) if (!G.deg[i]) que[tl++] = i;
while (hd < tl) {
int p = que[hd++];
maxd = std::max(maxd, dist[p]);
for (REG int i = G.head[p]; ~i; i = G.edge[i].next) {
int v = G.edge[i].v;
if (!(--G.deg[v])) { dist[v] = dist[p] + 1; que[tl++] = v; }
}
}
}
void dfs(int u) {
vis[u] = dp[u] = 1;
if (size[u]) inf[u] = 1;
for (int i = G.head[u]; ~i; i = G.edge[i].next) {
int v = G.edge[i].v, w = G.edge[i].w;
if (!vis[v]) dfs(v);
inc(dp[u], dp[v]);
positive[u] |= (positive[v] | (w > 0));
inf[u] |= inf[v];
}
}
//Rhein_E