【宽搜】ECNA 2015 E Squawk Virus (Codeforces GYM 100825)

题目链接：

　　http://codeforces.com/gym/100825

题目大意：

　　N个点M条无向边，(N<=100,M<=N(N-1)/2),起始感染源S，时间T(T<10)，每个感染源会在1个单位时间内给与自己相连的所有点传递与自身病毒数相等的病毒，然后自己的病毒数归零，被感染点在1个单位时间之后会收到病毒。

　　求T时刻这张图上的总病毒数。(初始时刻为0，S带有1个病毒)

题目思路：

　　【宽搜】

　　这题因为T很小，N也很小所以可以暴力宽搜，把图按时间奇偶分成两层，每次病毒都从一层中的感染源传递到另一层中与感染源相邻的点。

　　最后统计答案即可。

  1 //
  2 //by coolxxx
  3 //#include<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<map>
  9 #include<stack>
 10 #include<queue>
 11 #include<set>
 12 #include<bitset>
 13 #include<memory.h>
 14 #include<time.h>
 15 #include<stdio.h>
 16 #include<stdlib.h>
 17 #include<string.h>
 18 //#include<stdbool.h>
 19 #include<math.h>
 20 #define min(a,b) ((a)<(b)?(a):(b))
 21 #define max(a,b) ((a)>(b)?(a):(b))
 22 #define abs(a) ((a)>0?(a):(-(a)))
 23 #define lowbit(a) (a&(-a))
 24 #define sqr(a) ((a)*(a))
 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 26 #define mem(a,b) memset(a,b,sizeof(a))
 27 #define eps (1e-10)
 28 #define J 10000
 29 #define mod 1000000007
 30 #define MAX 0x7f7f7f7f
 31 #define PI 3.14159265358979323
 32 #define N 104
 33 #define M 10004
 34 using namespace std;
 35 typedef long long LL;
 36 double anss;
 37 LL aans;
 38 int cas,cass;
 39 int n,m,lll,ans;
 40 int s,t;
 41 int last[N];
 42 LL d[2][N];
 43 int q[2][N];
 44 bool u[2][N];
 45 struct edge
 46 {
 47     int next,to;
 48 }a[M];
 49 void add(int x,int y)
 50 {
 51     a[++lll].to=y;
 52     a[lll].next=last[x];
 53     last[x]=lll;
 54 }
 55 void spfa()
 56 {
 57     int i,now,to,k=1,tt,l[2],r[2];
 58     mem(d,0);mem(u,0);
 59     l[0]=l[1]=r[0]=r[1]=0;
 60     for(i=last[s];i;i=a[i].next)
 61     {
 62         q[0][++r[0]]=a[i].to;
 63         d[0][a[i].to]=1;
 64     }
 65     for(tt=0;tt<t-1;tt++)
 66     {
 67         k=tt&1;
 68         while(l[k]<r[k])
 69         {
 70             now=q[k][++l[k]];
 71             for(i=last[now];i;i=a[i].next)
 72             {
 73                 to=a[i].to;
 74                 d[1-k][to]+=d[k][now];
 75                 if(!u[1-k][to])
 76                 {
 77                     u[1-k][to]=1;
 78                     q[1-k][++r[1-k]]=to;
 79                 }
 80             }
 81         }
 82         l[k]=r[k]=0;
 83         mem(d[k],0);mem(u[k],0);
 84     }
 85     for(i=1;i<=n;i++)
 86         aans+=d[1-k][i];
 87 }
 88 int main()
 89 {
 90     #ifndef ONLINE_JUDGE
 91     freopen("1.txt","r",stdin);
 92 //    freopen("2.txt","w",stdout);
 93     #endif
 94     int i,j,k;
 95     int x,y,z;
 96 //    init();
 97 //    for(scanf("%d",&cass);cass;cass--)
 98 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 99 //    while(~scanf("%s",s))
100     while(~scanf("%d",&n))
101     {
102         aans=0;lll=0;mem(last,0);
103         scanf("%d%d%d",&m,&s,&t);
104         s++;
105         for(i=1;i<=m;i++)
106         {
107             scanf("%d%d",&x,&y);
108             x++,y++;
109             add(x,y),add(y,x);
110         }
111         if(t==0){puts("0");continue;}
112         spfa();
113         printf("%I64d
",aans);
114     }
115     return 0;
116 }
117 /*
118 //
119 
120 //
121 */

View Code