PowerOJ1180-矩阵快速幂

1180: 寻找大黄 SPJ

Time Limit: 11000 MS Memory Limit: 2097152 KB
Total Submit: 26 Accepted: 5 Page View: 32
Submit Status Discuss

    总所周知，大黄经常到处跑出去玩。对，没错，就是今天！院赛啊！大黄，又双叒叕跑出去耍了，把院赛的事情都搞忘了。无奈，我们只能让小梁晨去找她了。梁晨预判，大黄现在肯定在绵阳市范围内。我们可以把绵阳市看做一个由nn个点mm条边组成的无向图，且我们西科大对应的点的编号为11。每一分钟，大黄会等概率地走到和她当前所在点相邻的点。现在距离大黄离开西科大已经kk分钟了。梁晨想知道，现在大黄停留在每一个点的概率。

    输入第一行有两个正整数      n,m,kn,m,k（      2≤n≤2002≤n≤200，      1≤m≤n×(n−1)21≤m≤n×(n−1)2，      0≤k≤1050≤k≤105）。分别代表绵阳市的点数，双向边的条数，和大黄离开西科大的时间。 接下来      mm行，每行两个正整数      ui,viui,vi，表示点      uiui和点      vivi存在一条双向边。保证给出的图没有重边和自环。  

    输出n个数，表示现在大黄停留在每一个点的概率。 要求绝对误差或者相对误差小于      10−610−6。  

       3 3 31 22 31 3     

       0.25 0.375 0.375     

题目大意：

给你一张无向图，初始在节点1 接下来k分钟你将等概率的移动到其他相连接的节点，每条边花费1分钟，

问k分钟后经过每个节点的概率是多少

题目思路：

刚看到这题时想的是bfs来做，，但是发现如果暴力的话可能会超内存，因为k太大了，，然后就像其他方法

记得之前做过一道类似的求u->v经过k条边的最短路，其实这一类都是属于邻接矩阵乘法的应用，所以就考虑

矩阵快速幂来解决，对于G[i][j]^k表示i->j经过k分钟的概率，所以我们就考虑如何构造矩阵，对于G[i][j]^1 我们

可以从题目给出的图来构造，首先记录下所有的边和点的度，所以对于边ij G[i][j] = 1.0/in[i] in[i]表示i的度

然后 ans = ans*G 因为初始时在1 所以ans[0][0] = 1 然后就是用快速幂来求

AC代码：

#include<bits/stdc++.h>
using namespace std;
 
struct Matrix
{
    double M[205][205];
};
Matrix M,ans;
 
int in[205];
int n,m,k;
struct st
{
    int x,y;
}s[40000];
 
Matrix cal(Matrix a,Matrix b,int x)
{
    Matrix c;
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<n;j++)
        {
            double sum = 0;
            for(int k=0;k<n;k++)
            {
                sum+=a.M[i][k]*b.M[k][j];
            }
            c.M[i][j] = sum;
        }
    }
    return c;
}
 
void sove()
{
    while(k)
    {
        if(k&1)
        {
            ans = cal(ans,M,1);
        }
        M =cal(M,M,n);
        k/=2;
    }
}
 
int main()
{
    cin>>n>>m>>k;
    memset(M.M,0,sizeof(M));
    memset(in,0,sizeof(in));
    for(int i=0;i<m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        x--,y--;
        in[x]++,in[y]++;
        s[i].x = x,s[i].y = y;
    }
    for(int i=0;i<m;i++)
    {
        int x = s[i].x,y = s[i].y;
        M.M[x][y] = (double)1.00/in[x];
        M.M[y][x] = (double)1.00/in[y];
    }
    memset(ans.M,0,sizeof(ans.M));
    ans.M[0][0] = 1.0;
    sove();
    for(int i=0;i<n;i++)
    {
        printf("%lf%c",ans.M[0][i],i==n-1?'\n':' ');
    }
 
    return 0;
}

PowerOJ1180-矩阵快速幂

1180: 寻找大黄 SPJ

Description

Input

Output