最优贸易和它神马.pptxVIP

最优贸易和它的神马们;最优贸易;【输入】 输入文件名为trade.in。 第一行包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。 第二行n个正整数，每两个正整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。 接下来m行，每行有3个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。 【输出】 输出文件trade.out共1行，包含1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。 【数据范围】 输入数据保证1号城市可以到达n号城市。 对于10%的数据，1≤n≤6。 对于30%的数据，1≤n≤100。 对于50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。 对于100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球价格≤100。 ;此题解法繁多，官方解法是缩点+拓扑排序…… 今天就来讲一下缩点的一种算法——Tarjan;Tarjan是神马？;Tarjan算法;【算法思想】;算法流程演示;返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。;返回节点3，继续有哪些信誉好的足球投注网站到节点4，把4加入堆栈。发现节点4向节点1有边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，所以LOW[3]=LOW[4]=1。;继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。;贴代码;算法原理总结;关于缩点;题目大意;回到最优贸易;DP策略;三项注意;1;2;3;One possible version;关于一种奇葩的Topsort写法;Procedure topsortplus; Begin Head:=1; Tail:=1; For i:=1 to n do if inv[i]=0 then Begin q[tail]:=I; Inc(tail); End; While head =tail do Begin now:=q[head]; for i:=1 to v[now] do begin dec(inv[g[now,i]]); if inv[g[now,i]]=0 then begin q[tail]:=g[now,i]; inc(tail); end; end; inc(head); end; ;由于本人并没有打过该题代码，所以在此不提供该题代码（前向星、tarjan、topsort*2、DFS……想吐血……） 如果有人对该题代码有兴趣，可以登录dxhisboy在TYVJ的号（也就是左广胜的马甲 ==!）;最后推荐几个题;木了