#P9740. 公交路线

    ID: 6366 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-桥low-link边双连通分量桥树贡献法位集加速背包带权树可达性最优定向定理

公交路线

题目描述

一座城市有 nn 个公交车站。规划的第 ii 条路线连接车站 uiu_i 和 viv_i。为每条路线选择一个通行方向。

联通度是满足从车站 aa 可以沿通行方向到达车站 bb 的有序对 (a,b)(a,b) 数量,其中 1≤a,b≤n1\le a,b\le n。车站可以不经过任何路线到达自身,所以 (a,a)(a,a) 也计入。

求所有定向方案中最大的联通度。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行两个整数 u,vu,v,表示一条连接车站 u,vu,v 的路线。

输出格式

输出一个整数,表示最大联通度。

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 的性质。

数据范围与约定

2≤n≤20002\le n\le 2000,n−1≤m≤n(n−1)/2n-1\le m\le n(n-1)/2。原无向图连通,且没有自环或重边。

测试点 nn 的上界 mm 的限制
1 10 m≤15m\le 15
2–3 m≤20m\le 20
4–9 2000 m=n−1m=n-1
10–12 m=n(n−1)/2m=n(n-1)/2
13–16 100 无额外限制
17–20 2000

输入量较大,请使用快速读入。

原题 PDF