Evolution(ZOJ 2853)
Problem Description
Evolution is a long, long process with extreme complexity and involves many species. Dr. C. P. Lottery is currently investigating a simplified model of evolution: consider that we have N (2 <= N <= 200) species in the whole process of evolution, indexed from 0 to N -1, and there is exactly one ultimate species indexed as N-1. In addition, Dr. Lottery divides the whole evolution process into M (2 <= M <= 100000) sub-processes. Dr. Lottery also gives an 'evolution rate' P(i, j) for 2 species i and j, where i and j are not the same, which means that in an evolution sub-process, P(i, j) of the population of species i will transform to species j, while the other part remains unchanged.
Given the initial population of all species, write a program for Dr. Lottery to determine the population of the ultimate species after the evolution process. Round your final result to an integer.
Input
The input contains multiple test cases!
Each test case begins with a line with two integers N, M. After that, there will be a line with N numbers, indicating the initial population of each species, then there will be a number T and T lines follow, each line is in format "i j P(i,j)" (0 <= P(i,j) <=1).
A line with N = 0 and M = 0 signals the end of the input, which should not be proceed.
Output
Notes
1.There will be no 'circle's in the evolution process.
2.E.g. for each species i, there will never be a path i, s1, s2, ..., st, i, such that P(i,s1) <> 0, P(sx,sx+1) <> 0 and P(st, i) <> 0.
3.The initial population of each species will not exceed 100,000,000.
4.There're totally about 5 large (N >= 150) test cases in the input.
Example
Let's assume that P(0, 1) = P(1, 2) = 1, and at the beginning of a sub-process, the populations of 0, 1, 2 are 40, 20 and 10 respectively, then at the end of the sub-process, the populations are 0, 40 and 30 respectively.
Sample Input
2 3 100 20 1 0 1 1.0 4 100 1000 2000 3000 0 3 0 1 0.19 1 2 0.05 0 2 0.67 0 0
Sample Output
120 0
My Code
这题本地上跑有可能会栈溢出，如果你的程序突然炸了，请无视。。。试了下网上的AC代码，用VS跑的话全都栈溢出。。。把栈保留大小设置大一点就行了。
#include
#include
using namespace std;
struct Matrix
{
double M[205][205]; //本地上跑可能会栈溢出。。。但提交上去能AC，问题不大
};
Matrix mul(Matrix m1, Matrix m2, int n)
{
Matrix m3;
memset(m3.M, 0, sizeof(m3.M));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
m3.M[i][j] += (m1.M[i][k] * m2.M[k][j]);
return m3;
}
Matrix pow(Matrix m, int k, int n)
{
Matrix ans;
memset(ans.M, 0, sizeof(ans.M));
for (int i = 0; i < n; i++)
ans.M[i][i] = 1;
while (k)
{
if (k & 1)
ans = mul(ans, m, n);
m = mul(m, m, n);
k >>= 1;
}
return ans;
}
int main()
{
int n, m, t;
Matrix a;
Matrix ans;
while (cin >> n >> m && n && m)
{
memset(a.M, 0, sizeof(a.M));
memset(ans.M, 0, sizeof(ans.M));
for (int i = 0; i < n; i++)
a.M[i][i] = 1;
for (int i = 0; i < n; i++)
cin >> ans.M[0][i];
cin >> t;
for (int i = 0; i < t; i++)
{
int u, v;
double p;
cin >> u >> v >> p;
a.M[u][v] += p; //还是构造个矩阵，怎么构造，自己手工画几下就知道了
a.M[u][u] -= p;
}
printf("%.0lf
",mul(ans, pow(a, m, n), n).M[0][n - 1]); //保留整数，四舍五入那种
}
return 0;
} 
OωO
