首页 > 代码库 > ZOJ 2974 Just Pour the Water

ZOJ 2974 Just Pour the Water

矩阵快速幂。

构造一个矩阵,$a[i][j]$表示一次操作后,$j$会从$i$那里得到水的比例。注意$k=0$的时候,要将$a[i][j]$置为$1$。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - 0;        c = getchar();    }}struct Matrix{    double A[25][25];    int R, C;    Matrix operator*(Matrix b);};Matrix X, Y, Z;int T,n,p;Matrix Matrix::operator*(Matrix b){    Matrix c;    memset(c.A, 0, sizeof(c.A));    int i, j, k;    for (i = 1; i <= R; i++)        for (j = 1; j <= b.C; j++)            for (k = 1; k <= C; k++)                c.A[i][j] = c.A[i][j] + A[i][k] * b.A[k][j];    c.R = R; c.C = b.C;    return c;}void init(){    Y.R = n; Y.C = n;    for (int i = 1; i <= n; i++) Y.A[i][i] = 1;    X.R = n; X.C = n;    Z.R = 1; Z.C = n;}void work(){    while (p)    {        if (p % 2 == 1) Y = Y*X;        p = p >> 1;        X = X*X;    }    Z = Z*Y;}int main(){    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        memset(X.A, 0, sizeof X.A);        memset(Y.A, 0, sizeof Y.A);        memset(Z.A, 0, sizeof Z.A);        for(int i=1;i<=n;i++) scanf("%lf",&Z.A[1][i]);        for(int i=1;i<=n;i++)        {            int K; scanf("%d",&K);            for(int j=1;j<=K;j++)            {                int id; scanf("%d",&id);                X.A[i][id]=1.0/K;            }            if(K==0)            {                X.A[i][i]=1.0;            }        }        scanf("%d",&p);        init();        work();        for(int i=1;i<=n;i++)        {            printf("%.2f",Z.A[1][i]);            if(i<n) printf(" "); else printf("\n");        }    }    return 0;}

 

ZOJ 2974 Just Pour the Water