Linear Ecosystem

題目鏈接：

http://acm.hust.edu.cn/vjudge/contest/127401#problem/B

Description

http://7xjob4.com1.z0.glb.clouddn.com/99b0fe905e5bd89a24c882832c93cc09

Input

The first line of the input file contains an integer, n, which is the number of ecosystems. For each case,
the first line contains the integer k which is the number of comorgs. Followed by k lines, where the i-th
line contains, αi,1, αi,2, . . . , αi,k, the coefficients of the transition equation for ci.

Output

For each test case, output ‘1’ if the ecosystem is potentially stable, otherwise output ‘0’. Output only
5 answers per line. There should be a blank space between any two output answers.

Sample Input

6
2
4 -2
-6 5
2
2 2
0 0
3
0.3 0.2 0.5
0.4 0.4 0.2
0 0.8 0.2
3
0.3 0.2 0.5
0 0 0
0 0.8 0.2
2
4 2.0
-6 5
2
1 0
0 1

Sample Output

1 0 1 0 0
1

題意：

對一個k元向量, 每次左乘一個k*k的矩陣得到新的向量.
問經過一定次數的左乘后，能否使得該向量不再變化. (同時要求此時向量非零)

題解：

設初始向量為A，矩陣為P.
由于每次矩陣P都是左乘A, 那么可以把若干個P合并. 則題目的條件是：
化簡為： 由于要求 所以 P-1 必須不可逆.
可以直接用高斯消元求P-1的秩，判斷是否可逆（滿秩即可逆）.

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #include <vector> #include <list> #define LL long long #define eps 1e-6 #define maxn 50 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;double a[maxn][maxn],x[maxn]; int equ,var;int Gauss() {int i,j,k,col,max_r;for(k=0,col=0;k<equ&&col<var;k++,col++){max_r = k;for(i=k+1;i<equ;i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r = i;if(fabs(a[max_r][col])<eps) return 0; //無解,有自由變元if(k != max_r){for(j=col;j<var;j++)swap(a[k][j],a[max_r][j]);swap(x[k],x[max_r]);}x[k]/=a[k][col];for(j=col+1;j<var;j++)a[k][j]/=a[k][col];a[k][col] = 1;for(i=0;i<equ;i++)if(i!=k){x[i] -= x[k]*a[i][k];for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col];a[i][col]=0;}}return 1; }vector<int> ans;int main(int argc, char const *argv[]) {//IN;int t; cin >> t;while(t--){memset(a, 0, sizeof(a));cin >> equ; var = equ;for(int i=0; i<equ; i++) {for(int j=0; j<var; j++) {cin >> a[i][j];}a[i][i] -= 1.0; /* P - 1 */}if(Gauss()) ans.push_back(0);else ans.push_back(1);}for(int i=0; i<ans.size(); i++) {printf("%d%c", ans[i], (i%5==4||i==ans.size()-1)?'\n':' ');}return 0; }

轉載于:https://www.cnblogs.com/Sunshine-tcf/p/5781711.html

總結

以上是生活随笔為你收集整理的UVALive 7455Linear Ecosystem （高斯消元）的全部內容，希望文章能夠幫你解決所遇到的問題。

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