1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 618  Solved: 217

[Submit][Status]

Description

农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治. 这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接. 在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为0的路口,且所有入度为0的路口都会有奶牛. 帮助FJ找出最忙碌的道路,即计算所有路径中通过某条道路的最大次数.答案保证可以用32位整数存储.

Input

第一行:两个用空格隔开的整数:N,M.

第二行到第M+1行:每行两个用空格隔开的整数ai,bi,表示一条道路从ai到bi.

Output

第一行: 一个整数,表示所有路径中通过某条道路的最大次数.

Sample Input

7 7 1 3 3 4 3 5 4 6 2 3 5 6 6 7

Sample Output

4 样例说明: 1 4 \ / \ 3 6 -- 7 / \ / 2 5 通向奶牛宿舍的所有路径: 1 3 4 6 7 1 3 5 6 7 2 3 4 6 7 2 3 5 6 7

HINT

Source

Silver

 题解:我想揍死这个出题人——题目中明明说好的32位整数就可以的,但是当我天真的交了个没开int64的程序时,WA!!!然后我换成了int64,别的啥都没改,AC!!!这这这。。。好了步入正题——其实只需要顺着来一遍求出从出发点到各个点的路径数,再反着求一遍从各个点到奶牛宿舍的路径数(不难写的递推,此题嘛,呵呵呵,连拓扑排序都免了。。。)然后每个边的通过次数=出发点到此边的源点的路径数×此边的汇点到奶牛宿舍的路径数,这样子,才O(2N+M),轻松水过。。。

 1 type
 2     point=^node;
 3     node=record
 4                g:longint;
 5                next:point;
 6     end;
 7 var
 8    i,j,k,m,n:longint;
 9    l:int64;
10    a,b:array[0..6000] of point;
11    c,d:array[0..6000] of int64;
12    p:point;
13 procedure add(x,y:longint);
14           var p:point;
15           begin
16                new(p);
17                p^.g:=y;
18                p^.next:=a[x];
19                a[x]:=p;
20 
21                new(p);
22                p^.g:=x;
23                p^.next:=b[y];
24                b[y]:=p;
25           end;
26 begin
27      readln(n,m);
28      for i:=1 to m do
29          begin
30               readln(j,k);
31               add(j,k);
32          end;
33      for i:=1 to n do
34          begin
35               p:=b[i];
36               if p=nil then
37                  c[i]:=1
38               else
39                   begin
40                        c[i]:=0;
41                        while p<>nil do
42                              begin
43                                   c[i]:=c[i]+c[p^.g];
44                                   p:=p^.next;
45                              end;
46                   end;
47          end;
48      d[n]:=1;
49      for i:=n-1 downto 1 do
50          begin
51               p:=a[i];
52               if p=nil then
53                  d[i]:=0
54               else
55                   begin
56                        d[i]:=0;
57                        while p<>nil do
58                              begin
59                                   d[i]:=d[i]+d[p^.g];
60                                   p:=p^.next;
61                              end;
62                   end;
63          end;
64      l:=0;
65      for i:=1 to n do
66          begin
67               p:=a[i];
68               while p<>nil do
69                     begin
70                          k:=c[i]*d[p^.g];
71                          //writeln(i,' ',p^.g,' - ',c[i],' ',d[p^.g]);
72                          if k>l then l:=k;
73                          p:=p^.next;
74                     end;
75          end;
76      writeln(l);
77 end.
78                  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Vamei实验室

“不给力啊,老湿!”:RSA加密与破解

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

5321
来自专栏ml

HDUOJ-----4512吉哥系列故事——完美队形I(LCIS)

吉哥系列故事——完美队形I Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2938
来自专栏数据结构与算法

P1018 乘积最大

题目描述 今年是国际数学联盟确定的“2000――世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智...

31412
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2917
来自专栏HansBug's Lab

3389: [Usaco2004 Dec]Cleaning Shifts安排值班

3389: [Usaco2004 Dec]Cleaning Shifts安排值班 Time Limit: 1 Sec  Memory Limit: 128 MB...

2585
来自专栏我是攻城师

Lucene+Solr+ElasticSearch查询匹配优化

3505
来自专栏lonelydawn的前端猿区

Node.js力破江苏网警刑侦科推理试题

月前,江苏网警 在微博发布了一套《2018年刑侦科目推理试题》,可谓难倒了诸多英雄好汉,评论区内更是一片皮皮之音。 @二向箔icon: 高考前班主任教过我们,...

3457
来自专栏高性能服务器开发

携程面试题

冬天,西风凛冽,天空阴沉,行人都急匆匆的奔走,到了家,烤着炉子,外边洋洋洒洒的下起了雪。知道什么是“晚来天欲雪”,什么是“红泥小火炉”。

4153
来自专栏数据结构与算法

BZOJ3668: [Noi2014]起床困难综合症(贪心 二进制)

21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm 一直坚持与起床困难综合症作斗争。通过研...

782
来自专栏PPV课数据科学社区

趣文 | 程序员们,都进来看看编程语言之父都有谁

1、PHP PHP之父,Rasmus Lerdorf,1994年,为了要维护个人网页而制作的一个简单的用Perl语言编写的程序。这些工具程序用来显示 Rasmu...

3597

扫码关注云+社区

领取腾讯云代金券