第一题

题目描述

已知一个有 $n$ 个点，$m$ 个边的有向无环带点权图，请你求出该图有多少种合法的拓扑排序，并且求出边权的序列按字典序最小的一个。如果没有合法的拓扑排序，请输出dldsgay!!1。

注：点从 $1$ 开始编号

时间限制：$1.0$s

空间限制：$64$MB

输入格式

第一行两个整数 $n$, $m$

其后 $m$ 行，每行三个整数 $u$, $v$, $w$, 表示从点 $u$ 到点 $v$ 存在一条权值为 $w$ 的有向边。可能有重边

输出格式

第一行分两种情况：

1. 若该图存在拓扑排序，输出拓扑排序的数量
2. 若该图不存在拓扑排序，输出dldsgay!!1

若第一行为情况1，则其后另有一行 $n$ 个整数，表示该图按点权字典序最小的拓扑排序

数据范围&说明

$2 \le n \le 3 \times 10 ^6,\ \ 1 \le m \le 5 \times 10^6$

这题难在数据范围……

第二题

题目描述

已知有 $n$ 个互相不连通的点, 请你求出至少需要连多少条有向边才能使该图成为一个双连通图。

同时，定义 $\operatorname {dis}_{i,j}$ 为点 $i$ 到点 $j$ 的最短路径，请你通过合理地给每一条你连的边赋一个互不相同的边权，使得

$\large{\sum\limits_{i=1}^n\sum\limits_{j=1}^n\operatorname{dis}_{i,j}}$

防止炸$\LaTeX$只能这样

最小。特别地，$\operatorname{dis}_{i,i}=0$

输入格式

一行一个整数 $n$，意思如题意

输出格式

第一行一个整数 $m$, 表示至少需要连得边的数量

接下来 $m$ 行，每行三个整数 $u$, $v$, $w$, 表示从点 $u$ 到点 $v$ 连接一条边权为 $w$ 的有向边

最后一行一个整数，表示在你的图中任意两点之间最短路径之和，答案对 $998244353$ 取模

数据范围&说明

$2 \le n \le 10^{12}$

我是不是该at下兔队

感激不尽