#3184. 立体交通

立体交通

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目限制

1000 ms 256 M

题目描述

自从有了立体交通,道路不再受平面的限制,可以不用有十字路口,就让两条道路互相穿越。

已知城市中共有 nn 个站点(编号 1n1 \sim n ),其中共有 mm单向道路。现在公交公司计划开设一些单行线的公交线路,需要保证起始站 ss 向终点站 tt 有通路连接,并且同一组 (s,t)(s,t) 仅开设一条线路

现在请问至多能够开设多少条线路?

注意:允许存在环线,即 s=ts=t 。且由于是单行线, (s,t)(s,t)(t,s)(t,s) 视为不同线路。

输入格式

第一行: 22 个整数 n,mn,m ,表示位置的数量和道路的数量。( 2N20002\le N\le 20000Mmin(2000,N(N1))0\le M\le min(2000,N(N-1)) ) 之后 mm 行:每行 22 个正整数 u,vu,v ,表示站点 uuvv 有一条单向道路,保证不存在自环。

输出格式

输出一个数表示至多开设的公交线路数量。

数据范围

对于 12.5%12.5\% 的数据, 2N10,0M102 \le N \le 10, 0 \le M \le 10

对于 100%100\% 的数据, 2N2000,0Mmin(2000,N(N1)),1ai,biN,aibi2 \le N \le 2000, 0 \le M \le \min(2000,N(N-1)), 1 \le a_i,b_i \le N, a_i \ne b_i

输入样例 1

3 3
1 2
2 3
3 2

输出样例 1

7

2024年CSP-J模拟测试6

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-8-31 12:00
结束于
2024-9-5 12:00
持续时间
120 小时
主持人
参赛人数
112