poj3249

显然是一道最短路径的题目，但是

1 ≤ n ≤ 100000, 0 ≤ m ≤ 1000000能轻松打爆dij+heap

怎么办？

挖掘题意，这是一个DAG图（有向无环图）

所以对于此类问题，我们有特殊的作法

对于DAG，拓扑序列在前的点的最短路一定会被先更新（值得思考）

所以我们只用对DAG做一次拓扑，然后依次更新最短路即可；（其实很像dp）

多个入度为0的点不影响结果；

再回到这题，由于给出的是点的权值

可以考虑拆点，将点i拆成点i1,i2，i1,i2之间连一条指向i2的有向边，权值为原先点的权值

原先所有入边连向i1，出边连i2，权值都是0，这样就搞定了

拆点的做法在后面的网络流中会经常用到（当然这题也可以不拆）

1 type link=^node;
 2      node=record
 3        po,len:longint;
 4        next:link;
 5      end;
 6 
 7 var w:array[0..200010] of link;
 8     v:array[0..200010] of boolean;
 9     c,r,q,d:array[0..200010] of longint;
10     n,m,ans,i,t,f,s,x,y:longint;
11     p,g:link;
12 function max(a,b:longint):longint;
13   begin
14     if a>b then exit(a) else exit(b);
15   end;
16 
17 procedure add(x,y,z:longint);  //邻接表
18   var p:link;
19   begin
20     new(p);
21     p^.po:=y;
22     p^.len:=z;
23     p^.next:=w[x];
24     w[x]:=p;
25   end;
26 
27 begin
28   while not eoln do
29   begin
30     readln(n,m);
31     for i:=1 to 2*n do
32       w[i]:=nil;
33     fillchar(r,sizeof(r),0);
34     fillchar(c,sizeof(c),0);
35     for i:=1 to n do  //拆点
36     begin
37       readln(x);
38       add(i+n,i,x);
39       inc(r[i]);
40       inc(c[i+n]);
41     end;
42     for i:=1 to m do  //建边
43     begin
44       readln(x,y);
45       add(x,y+n,0);
46       inc(r[y+n]);
47       inc(c[x]);
48     end;
49     s:=0;
50     fillchar(v,sizeof(v),false);
51     fillchar(q,sizeof(q),0);
52     for i:=1 to 2*n do   //先找入度为0的点
53       if r[i]=0 then
54       begin
55         inc(s);
56         v[i]:=true;
57         q[s]:=i;
58       end;
59     f:=0;
60     while s<2*n do      //生成拓扑序列
61     begin
62       inc(f);
63       p:=w[q[f]];
64       while p<>nil do
65       begin
66         dec(r[p^.po]);
67         if r[p^.po]=0 then
68         begin
69           inc(s);
70           q[s]:=p^.po;
71         end;
72         p:=p^.next;
73       end;
74     end;
75     for i:=1 to 2*n do     //d[i]表示从某个入度为0的点到达当前点的最大距离
76       if v[i] then d[i]:=0 else d[i]:=-2147483647;
77     ans:=-2147483647;
78     for i:=1 to 2*n do
79     begin
80       f:=q[i];
81       p:=w[f];
82       g:=nil;
83       while p<>nil do   //按照拓扑序列依次更新所有到达的点
84       begin
85         t:=p^.po;
86         d[p^.po]:=max(d[p^.po],d[f]+p^.len);
87         g:=p;
88         p:=p^.next;
89         dispose(g);   //注意这题多测加上巨大的n，m很有可能把链表挤爆，所以及时释放掉空间
90       end;
91     end;
92     for i:=1 to 2*n do
93       if c[i]=0 then ans:=max(d[i],ans);
94     writeln(ans);
95   end;
96 end.      

View Code

拓扑序列复杂度O(m)，最短路O(m)

所以总的复杂度O(m)

转载于:https://www.cnblogs.com/phile/p/4473284.html