| 找啊找啊找朋友 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB |
| Total submit users: 14, Accepted users: 11 |
| Problem 11548 : No special judgement |
| Problem description |
| 小明和小红是一对好朋友，小明一有空就去找小红玩。可是小红飘忽的行踪让小明非常是伤脑筋。 小红居住的小区的地下有当年抗战时期留下的地道，小红平时总是喜欢在这些地道里走来走去。 小红所在的小区有N个地道出入口，依次标记为0到N-1，小明想知道当他到小区的时候小红会在那个地道出入口，这样他就不会走冤枉路了。 小红初始的时候会在D号出入口，小明会在T个单位之间之后到达，小红每一个单位时间一定会从她当前所在的出入口通过地道走到与之相邻的出入口，假设有多个出入口与之相邻，那么她会等概率随机选择一个进行移动，即假设有3个，那么走到不论什么一个的概率都是1/3。4个的话就是1/4。 如今给你整个小区地道的布局。请你告诉小明T个单位时间之后，小红在各个出入口的概率是多少。 |
| Input |
| 多组例子，请处理到文件结束。 每组例子第一行包含3个整数，N (2 <= N <= 50), D(0 <= D < N), T(1 <= T <= 10^9). 接下来包括一个N * N的矩阵,每一个元素仅仅可能是0或者1,第i行第j列是1表示i号出入口与j号出入口有通道相连.数据保证各出入口都是联通的,并且矩阵一定是对称矩阵,当i==j时,元素的值一定是0. |
| Output |
| 对每组例子,首先输出一行Case #k:,k从1開始. 接着输出N个数,表示在出入口0到N-1的概率,保留2位小数,数字之间用一个空格隔开 |
| Sample Input |
2 0 2 |
| Sample Output |
Case #1: |
| Problem Source |
| HNU Contest |
解析：我好像是用的矩阵做的。用到矩阵的高速幂
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX(a,b) a>b? a:b
#define MIN(a,b) a<b?a:b
#define Max 1000000000
using namespace std;
int n,d,t;
double s[55][55],sum[55][55];
void cmp(double (*a)[55],double (*b)[55])//求矩阵a乘以矩阵b再存储在a中
{//跟度娘问候了半天。也没找到一个优化的计算法，仅仅有这个n^3的，还是抱着看看是否超时的想法来提交的。。
int i,j,k,l;
double c[55][55]={0};
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]>0)//这个也算剪枝吧
{
for(k=0;k<n;k++)
c[i][k]+=a[i][j]*b[j][k];
}
for(i=0;i<n;i++)//把结果存到a里面去
for(j=0;j<n;j++)
a[i][j]=c[i][j];
}
void ksm()//标准高速幂，喜欢的带回家
{
int i,j,k,l;
memset(sum,0,sizeof(sum));
sum[d][d]=1;//起点在d，那么就记录在sum[d][d]
while(t>0)
{
if(t%2==1)cmp(sum,s);
t/=2;
cmp(s,s);
}
}
int main(void)
{
int i,j,k,l,cas=1;
double c;
while(scanf("%d%d%d",&n,&d,&t)!=EOF)
{
for(i=0;i<n;i++)
{
c=0;
for(j=0;j<n;j++)
{
scanf("%lf",&s[i][j]);
c+=s[i][j];
}
if(c)
for(j=0;j<n;j++)
s[i][j]/=c;
}
ksm();
printf("Case #%d:\n",cas++);
for(i=0;i<n;i++)//我也不知道咋滴。所有打出来结果仅仅有第d行才有数据，应该是矩阵的特性吧。
printf("%.2lf%c",sum[d][i],i==n-1?'\n':' ');
}
return 0;
}