BZOJ—— 3402: [Usaco2009 Open]Hide and Seek 捉迷藏

http://www.lydsy.com/JudgeOnline/problem.php?id=3402

Description

贝茜在和约翰玩一个“捉迷藏”的游戏．

她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．

Input

第1行输入两个整数N和M，之后M行每行输入两个整数，表示一条路的两个端点．

Output

仅一行，输出三个整数．第1个表示安全牛棚（如果有多个，输出编号最小的）；第2个表示牛棚1和安全牛棚的距离；第3个表示有多少个安全的牛棚．

Sample Input

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

Sample Output

4 2 3

HINT

Source

Silver

SPFA 对于一个到达过的点，更新他的最小值，没到达的更新当前值，

记录到达每个点的次数，最后找出最长距离判断判断就好了。

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <queue>
 4 
 5 inline void read(int &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 
12 const int M(50005);
13 const int N(20005);
14 
15 int n,m,head[N],sumedge;
16 int _v[M<<1],_nex[M<<1];
17 inline void ins(int u,int v)
18 {
19     _v[++sumedge]=v,_nex[sumedge]=head[u];head[u]=sumedge;
20     _v[++sumedge]=u,_nex[sumedge]=head[v];head[v]=sumedge;
21 }
22 
23 bool inq[N];
24 int dis[N],cnt[N],id[M];
25 
26 inline void SPFA(int s)
27 {
28     for(int i=1; i<=n; ++i) dis[i]=-1;
29     std:: queue<int>que;
30     dis[s]=0; que.push(s);
31     for(int u,v; !que.empty(); )
32     {
33         u=que.front(); que.pop(); inq[u]=0;
34         for(int i=head[u]; i; i=_nex[i])
35         {
36             if(dis[_v[i]]==-1)
37             {
38                 cnt[_v[i]]++;
39                 dis[_v[i]]=dis[u]+1;
40                 if(!inq[_v[i]])
41                 {
42                     que.push(_v[i]);
43                     inq[_v[i]]=true;
44                 }
45             }
46             else if(dis[_v[i]]>dis[u]+1)
47             {
48                 cnt[_v[i]]++;
49                 dis[_v[i]]=dis[u]+1;
50                 if(!inq[_v[i]])
51                 {
52                     que.push(_v[i]);
53                     inq[_v[i]]=true;
54                 }
55             }
56         }
57             
58     }
59 }
60 
61 int Presist()
62 {
63     read(n),read(m);
64     for(int u,v; m--; )
65         read(u),read(v),ins(u,v);
66     SPFA(1); int now=-1,pos,num;
67     for(int i=1; i<=n; ++i)
68       if(dis[i]>now) now=dis[i],pos=i,num=cnt[i];
69     printf("%d %d ",pos,now); num=0;
70     for(int i=1; i<=n; ++i) num+=(dis[i]==now);
71     printf("%d
",num);
72     return 0;
73 }
74 
75 int Aptal=Presist();
76 int main(int argc,char**argv){;}