首页 > 代码库 > 1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

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

2024-08-07 23:20:09   220人阅读

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           begin16                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 begin27      readln(n,m);28      for i:=1 to m do29          begin30               readln(j,k);31               add(j,k);32          end;33      for i:=1 to n do34          begin35               p:=b[i];36               if p=nil then37                  c[i]:=138               else39                   begin40                        c[i]:=0;41                        while p<>nil do42                              begin43                                   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 do50          begin51               p:=a[i];52               if p=nil then53                  d[i]:=054               else55                   begin56                        d[i]:=0;57                        while p<>nil do58                              begin59                                   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 do66          begin67               p:=a[i];68               while p<>nil do69                     begin70                          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

 

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


联系
我们