【XJOI】path 题解

题目出自学军中学
（我不记得题目叫什么名字了，这个题目是我乱起的）

题目大意

  给出一幅 $n$ 个点的有向图，边长是 $1$。
  求最大的 $k$，使得对于任意正整数 $L$（$L<=$图中最长路径的长度），长度为 $L$ 的路径数是 $O(L^k)$ 的。若不存在则输出 -1。
  $n \le 10^5$

这是一道读题题

  读懂题就会做了

题解

  题目的意思是，对于任意长度 $L$，其方案数必须是一个多项式，最高次$<=k$。

  首先如果图中存在一个复杂环（就是存在环套环的意思），那么这里能贡献的方案数就是指数级别的了（走一下 A 环，再走一下 B 环，再走一下 A 环……），所以输出 -1。

  于是就变成了一个只有简单环的图。我们缩点得到一幅 DAG。
  对于 DAG 上的某一条路径，有些点原来是环，假设有 $x$ 个这样的点。我现在走这条路径，假设这些环点我分别走了 $c_1、c_2、……、c_x$ 次。
  考虑这条路径对长度 $L$ 的贡献，相当于我枚举 $c_1、c_2、……、c_x$，使得它们加起来是 $L$。因此方案数是 $O(L^{x-1})$

  因此在这个 DAG 上求一条点权最大的路径（若该点原来是环，点权就为 1，否则为 0），减 1 就是答案。