#P9740. 公交路线
公交路线
题目描述
一座城市有 个公交车站。规划的第 条路线连接车站 和 。为每条路线选择一个通行方向。
联通度是满足从车站 可以沿通行方向到达车站 的有序对 数量,其中 。车站可以不经过任何路线到达自身,所以 也计入。
求所有定向方案中最大的联通度。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示一条连接车站 的路线。
输出格式
输出一个整数,表示最大联通度。
5 4
1 2
1 3
1 4
1 5
13
6 7
1 2
2 3
1 3
1 4
4 5
5 6
6 4
27
样例 3、4、5 见题目附件中的 bus3.in、bus4.in、bus5.in 和各自的 .out 文件,依次满足测试点 3、7、13 的性质。
数据范围与约定
,。原无向图连通,且没有自环或重边。
| 测试点 | 的上界 | 的限制 |
|---|---|---|
| 1 | 10 | |
| 2–3 | ||
| 4–9 | 2000 | |
| 10–12 | ||
| 13–16 | 100 | 无额外限制 |
| 17–20 | 2000 |
输入量较大,请使用快速读入。