生化危机
发布时间: 2015年10月10日 18:05 时间限制: 1000ms 内存限制: 256M
X博士想造福人类, 研发一种可以再生肢体的药物, 可是很不幸......研究失败了, 他在蜥蜴身上实验的时候, 蜥蜴发生了变异, 更糟糕的是, 蜥蜴逃出了生化实验室.
恐怖的事情发生了, 疫情以X博士所在的城市为中心向四周扩散开, 最终, 整个地球上的城市都被感染了.假设整个地球一共有N个城市, 这N个城市是连通的, 有N-1条通道把他们连接起来.病毒会以一座城市为中心,在一天的时间内, 会把和他相连的周围的所有城市感染. 那么, 多少天的时间, 整个地球的城市都感染呢?
第一行输入一个T(T <= 50), 表示一共有T组测试数据.
每组数据第一行两个数n, k. n表示有n(2 <= n <= 10000)个城市, 代表城市1-n, k是X博士所在的城市.
接下来n-1行, 每行有两个数u, v, 表示城市u和v之间有一条通道.
每组数据第一行输出第一个数 x , 表示整个地球感染需要x天.
接下来 x 个数, 第i个数表示第i天感染了城市的数量.
(注意， 每组数据第二行每个数据后边都有一个空格）
复制
2 3 1 1 2 2 3 3 2 1 2 2 3
3 1 1 1 2 1 2
一道邻接表存图+BFS的好题。重点是邻接表，vector使用链式存储，适用于稀疏图，存多少点开多少点，避免了邻接矩阵存图导致的空间浪费，而且减少了无谓的枚举，也能大大提高时间效率。邻接表存储原理：可以把vector的v数组实际可以看成一个二维数组v[][]，第一个下标表示u->v边的左端点u，第二个下标是以u出度边的个数，元素值代表v。当然这只适用于各边权值相同的情况（对这道题来说已经足够，带权边的图可使用struct）。记录BFS扩展次数，每扩展一次，记录下感染数量即可。
#include<stdio.h> #include<string.h> #include<vector> #include<queue> using namespace std; struct Node{ int x,s; }node; int main() { int t,n,k,x,y,tx,cc,c,i; int a[10005],b[10005]; queue<Node> q; vector<int> v[10005]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(i=1;i<=n;i++){ v[i].clear(); } for(i=1;i<n;i++){ scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); b[k]=1; node.x=k; node.s=1; q.push(node); cc=0;c=1; while(q.size()){ if(a[q.front().s]==0){ a[++cc]=c; c=0; } for(i=0;i<v[q.front().x].size();i++){ //切记从0开始 tx=v[q.front().x][i]; if(b[tx]==0){ c++; b[tx]=1; node.x=tx; node.s=q.front().s+1; q.push(node); } } q.pop(); } printf("%d ",cc); for(i=1;i<=cc;i++){ printf("%d ",a[i]); } printf(" "); } return 0; }