Solve

USACO 2.3.5 Concom

这道题过了，但是这道题就不贴时间和程序的全部了，因为我原来用超级复杂的邻接表做的，最后的一个数据没有过(第9个)，后来发现邻接矩阵这么简单，于是此刻我充分感受到了KISS原则的宝贵，毕竟usaco的第二章不会考到多么精尖的算法，与其用2、3个小时编写一个0s的程序，倒不如用40min写一个0.1s的程序的性价比高！！！

邻接矩阵:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure DFS (s:byte);
var
  i:byte;
begin
  if vis[s] then
    exit;
  vis[s]:=true;
  for i:=1 to m do
  begin
    inc(cx[i],con[s,i]);
    if cx[i]>50 then
    begin
      own[i]:=true;
      DFS(i);
    end;
  end;
end;

邻接表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
procedure dfs1(x,y:integer);
var i,j:integer;
begin
 if b[x]=false then exit;
 b[x]:=false;
 if x<>y then
 begin
  for i:=1 to a[x].next do
   if (a[x].jie[i]=y) then
    begin a[x].flag[a[x].jie[i]]:=true; end;
   for i:=1 to a[x].next do
   begin
    for j:=1 to a[y].next do
     if (a[y].jie[j]=a[x].jie[i])and(not a[x].flag[i]) then
     begin
      a[y].jdata[j]:=a[x].jdata[i]+a[y].jdata[j];
      a[x].flag[i]:=true;
     end;
   end;
   for i:=1 to a[x].next do
    if (not a[x].flag[i])and(a[x].jie[i]<>y)then
    begin
     inc(a[y].next);
     a[y].jie[a[y].next]:=a[x].jie[i];
     a[y].jdata[a[y].next]:=a[x].jdata[i];
    end;
 end;
 for i:=1 to a[x].next do
 begin
  if (a[x].jie[i]<>y)and b[a[x].jie[i]] and (a[x].jdata[i]>50)
   then
   begin
    dfs1(a[x].jie[i],y);
   end;
 end;
end;

差距很大吧，不但如此，矩阵不必排序，而表则还另需排序，就算是我练习编程吧。RP……

后记

本文是原新浪博客的移植，附：全部USACO题目解答。