8.3.4 奥运

奥运

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 82 Accepted Submission(s): 40

Problem Description

北京迎来了第一个奥运会，我们的欢呼声响彻中国大地，所以今年的奥运金牌 day day up!
比尔盖兹坐上鸟巢里，手里摇着小纸扇，看的不亦乐乎，被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了，他对自己说，我自己也来举办一个奥运会，看谁的更火。不过他的奥运会很特别：
1 参加人员必须是中国人；
2 至少会加法运算（因为要计算本人获得的金牌数）
他知道中国有很多的名胜古迹，他知道自己在t1 到 t2天内不可能把所有的地方都玩遍，所以他决定指定两个地方v1,v2，如果参赛员能计算出在t1到t2天（包括t1,t2）内从v1到v2共有多少种走法(每条道路走需要花一天的时间，且不能在某个城市停留,且t1=0时的走法数为0)，那么他就会获得相应数量的金牌，城市的总数<=30,两个城市间可以有多条道路
，每条都视为是不同的。

Input

本题多个case，每个case：
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1，p2 表示城市p1到p2有道路，并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行，每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)

Output

对于每组数据中的每个参赛人员输出一个整数表示他获得的金牌数（mod 2008）

Sample Input

Sample Output

0
1506
0

思路：用map和邻接矩阵

路径条数就是把邻接矩阵乘起来

想想为什么？

我们怎么计算路径条数？

假设计算到a的路径条数=sigma({集合b：所有能到达a的点}的路径条数*(集合b的每一个对应元素到a)有多少条路)

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <string>
  6 #include <cstdlib>
  7 #include <map>
  8 using namespace std;
  9 
 10 typedef long long ll;
 11 typedef double dd;
 12 const int maxn=10010;
 13 const int mod=2008;
 14 map<int,int> mp;
 15 int n,v1,v2,V1,V2,query,T,t1,t2,m,x,y,ans;
 16 struct matrix
 17 {
 18     int m[31][31];
 19 } c,r[maxn],base;
 20 
 21 void close()
 22 {
 23 exit(0);
 24 }
 25 
 26 void print(matrix a)
 27 {
 28     for (int i=1;i<=n;i++)
 29     {
 30         for (int j=1;j<=n;j++)
 31             printf("%d ",a.m[i][j]);
 32         puts("");
 33     }
 34 }
 35 
 36 matrix mul(matrix a,matrix b)
 37 {
 38     memset(c.m,0,sizeof(c.m));
 39     for (int i=1;i<=n;i++)
 40         for (int j=1;j<=n;j++)
 41             for (int k=1;k<=n;k++)
 42             {
 43                 c.m[i][j]+=a.m[i][k]*b.m[k][j];
 44                 c.m[i][j] %= mod;
 45             }
 46     return c;
 47 }
 48 
 49 void init()
 50 {
 51 
 52 }
 53 
 54 int main ()
 55 {
 56     while (scanf("%d",&T)!=EOF)
 57     {
 58         n=0;
 59         mp.clear();
 60         memset(base.m,0,sizeof(base.m));
 61         while (T--)
 62         {
 63             scanf("%d %d",&x,&y);
 64             if (mp[x]==0)
 65             {
 66                 n++;
 67                 mp[x]=n;
 68             }
 69             if (mp[y]==0)
 70             {
 71                 n++;
 72                 mp[y]=n;
 73             }
 74             base.m[mp[x]][mp[y]]++;
 75             // X -> Y
 76         }
 77         m=10000; //Need to be changed!
 78         r[1]=base;
 79         for (int i=2;i<=m;i++)
 80             r[i]=mul(r[i-1],base);
 81         scanf("%d",&query);
 82         while (query--)
 83         {
 84             ans=0;
 85             scanf("%d %d %d %d",&v1,&v2,&t1,&t2);
 86             if (t1>t2 || t2==0)
 87             {
 88                 ans=0;
 89             }
 90             else
 91             {
 92                 if (mp[v1]==0 || mp[v2]==0)
 93                     ans=0;
 94                 else
 95                 {
 96                     V1=mp[v1];
 97                     V2=mp[v2];
 98                     for (int i=max(1,t1);i<=t2;i++)
 99                     {
100 
101                         ans+=r[i].m[V1][V2];
102                         ans %= mod;
103                     }
104                 }
105             }
106             printf("%d
",ans);
107         }
108     }
109     return 0;
110 }