原題鏈接

描述

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.

輸入

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.

輸出

For each test case, output the rounded-to-integer population of the ultimate species after the whole evolution process. Write your answer to each test case in a single line.

注意

There will be no 'circle's in the evolution process.
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.
The initial population of each species will not exceed 100,000,000.
There're totally about 5 large (N >= 150) test cases in the input.

舉例

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.

樣例輸入

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

樣例輸出

120
0

思路

第一關是讀懂題意，我這種英語渣看了半天才看懂。
看懂題意后就很簡單了，構建矩陣，然后標準的矩陣快速冪，注意最后取整就好。
順便這里一個小插曲，我的devcpp報段錯誤，似乎是我把矩陣開太大的原因，但是數據范圍就這么大，提交之后卻AC了，也是尷尬。

代碼

#include <cstdio> #include<cstring> #define ll long long #define maxn 201 using namespace std;int k; int n;struct Mat {double f[maxn][maxn];void cls(){memset(f, 0, sizeof(f));}//全部置為0 Mat() {cls();}friend Mat operator * (Mat a, Mat b){Mat res;for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)for(int k = 0; k < n; k++)res.f[i][j] += a.f[i][k] * b.f[k][j];return res;} };Mat quick_pow(Mat a) { Mat ans;for(int i = 0; i < n; i++) ans.f[i][i] = 1;int b = k;while(b != 0) {if(b & 1) ans = ans * a;b >>= 1;a = a * a;}return ans; }int main() {while(~scanf("%d %d", &n, &k)){if(n + k == 0) break;Mat A, B;for(int i = 0; i < n; i++) A.f[i][i] = 1;for(int i = 0; i < n; i++)scanf("%lf", &B.f[i][0]);int t; scanf("%d", &t);while(t--){int x, y;double p;scanf("%d %d %lf", &x, &y, &p);A.f[x][x] -= p;A.f[y][x] += p;}A = quick_pow(A);B = A * B;printf("%.0lf\n", B.f[n-1][0]);}return 0; }

轉載于:https://www.cnblogs.com/HackHarry/p/8399047.html

總結

以上是生活随笔為你收集整理的ZOJ 2853的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。