加载中…
个人资料
sacredfantasy
sacredfantasy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,313
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

usaco 2.3.5 concom

(2009-04-26 01:57:26)
标签:

usaco

2.3.5

concom

杂谈

分类: OI题解

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

以下是片断:

矩阵:

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;

表:

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......

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有