3361: [Usaco2004 Jan]培根距离

3361: [Usaco2004 Jan]培根距离

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 16  Solved: 13

[Submit][Status][Discuss]

Description

    贝茜和其他奶牛联系是通过一连串的中间奶牛传递的,所以当第一头牛和贝茜联系,第二头牛和第一头牛联系,第三头牛和第二头牛联系,…一贝茜就能依次联系到其中的每一头奶牛. 联系长度是指传递过程中涉及的奶牛的数目(不包括贝茜).任何一头奶牛(不包括贝茜)的培根距离是指从贝茜到该奶牛的最小联系长度.最小的培根距离是1(当贝茜能够直接与该奶牛联系时).约输有C头牛,编号1到C,贝茜是1号.有P(1≤P≤10000)组奶牛相互联系.请找到最大的培根距离.

Input

    第1行:C和P.

    第2到P+1行:每行两头牛,它们之间有联系.

Output

    输出最大培根距离.

Sample Input

6 7 1 2 2 3 2 4 3 4 3 5 4 5 6 5

Sample Output

4 样例说明 从贝茜到6奶牛的距离是4.联系路径(2,4,5,6)和(2,3,5,6)都适合

HINT

Source

Orange

题解:spfa模板题,水水哒

在这个里面加入了一个新的优化方法,昨天在wnjxyk的空间里面看到的(OTLwnjxyk),在spfa入队前,可以在队列内的值进行判重操作,这样子可以提高速度,而且必要时可以起到压缩队列所用空间的作用,可以将队列有效长度控制在N以内,这样子必要时只需要开一个循环队列即可解决空间问题,GET!!!(OTLwnjxyk)

 1 type
 2         point=^node;
 3         node=record
 4                 g,w:longint;
 5                 next:point;
 6         end;
 7 var
 8         i,j,k,l,m,n,f,r:longint;
 9         p:point;
10         a:array[0..100000] of point;
11         b,c:array[0..100000] of longint;
12         d:array[0..1000000] of longint;
13 procedure add(x,y,z:longint);inline;
14         var p:point;
15         begin
16                 new(p);p^.g:=y;p^.w:=z;
17                 p^.next:=a[x];a[x]:=p;
18         end;
19 begin
20         readln(n,m);
21         for i:=1 to n do a[i]:=nil;
22         for i:=1 to m do
23                 begin
24                         readln(j,k);
25                         add(j,k,1);add(k,j,1);
26                 end;
27         fillchar(b,sizeof(b),0);
28         fillchar(c,sizeof(c),0);
29         fillchar(d,sizeof(d),0);
30         f:=1;r:=2;
31         d[1]:=1;c[1]:=1;b[1]:=1;
32         while f<r do
33                 begin
34                         p:=a[d[f]];
35                         while p<>nil do
36                                 begin
37                                         if ((b[p^.g]=0) or ((b[p^.g]=1) and (b[p^.g]>(b[d[f]]+p^.w)))) and (c[p^.g]=0) then
38                                                 begin
39                                                         b[p^.g]:=b[d[f]]+p^.w;
40                                                         c[p^.g]:=1;
41                                                         d[r]:=p^.g;
42                                                         inc(r);
43                                                 end;
44                                         p:=p^.next;
45                                 end;
46                         c[d[f]]:=0;
47                         inc(f);
48                 end;
49         for i:=1 to n do dec(b[i]);
50         l:=0;
51         for i:=1 to n do if b[i]>l then l:=b[i];
52         writeln(l);
53 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

3389: [Usaco2004 Dec]Cleaning Shifts安排值班

3389: [Usaco2004 Dec]Cleaning Shifts安排值班 Time Limit: 1 Sec  Memory Limit: 128 MB...

2555
来自专栏数据结构与算法

Day3上午解题报告

预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

2935
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2847
来自专栏HansBug's Lab

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec  Memory ...

2868
来自专栏高性能服务器开发

携程面试题

冬天,西风凛冽,天空阴沉,行人都急匆匆的奔走,到了家,烤着炉子,外边洋洋洒洒的下起了雪。知道什么是“晚来天欲雪”,什么是“红泥小火炉”。

3783
来自专栏HansBug's Lab

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

2957
来自专栏ml

HDUOJ-----4506小明系列故事——师兄帮帮忙

小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2897
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

1957
来自专栏技术博客

设计模式之前奏(UML类图)

本人菜菜一个,最近一直在博客园游走闲逛,看到了各种技术,各种各种……。便看到了大话设计模式这本书,下了电子版的看了看第一章,感觉相当不错,不仅通俗易懂,而且与实...

2193
来自专栏数据结构与算法

P1828 香甜的黄油 Sweet Butter

题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜...

3007

扫码关注云+社区

领取腾讯云代金券