农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治. 这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接. 在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为0的路口,且所有入度为0的路口都会有奶牛. 帮助FJ找出最忙碌的道路,即计算所有路径中通过某条道路的最大次数.答案保证可以用32位整数存储.
第一行:两个用空格隔开的整数:N,M.
第二行到第M+1行:每行两个用空格隔开的整数ai,bi,表示一条道路从ai到bi.
第一行: 一个整数,表示所有路径中通过某条道路的最大次数.
题解：我想揍死这个出题人——题目中明明说好的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
1638: [Usaco2007 Mar]Cow Traffic 奶牛交通
原文：http://www.cnblogs.com/HansBug/p/4163827.html