fork(2) download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. #include<map>
  5. #include<algorithm>
  6. #include<climits>
  7. #include<cstdio>
  8. #include<cmath>
  9. #define INF INT_MAX
  10.  
  11. using namespace std;
  12.  
  13. struct fract{
  14. 	int bunbo;
  15. 	int bunsi;
  16. 	fract(int a,int b){
  17. 		bunbo = a;
  18. 		bunsi = b;
  19. 	}
  20. 	fract(){
  21. 		bunbo = 1;
  22. 		bunsi = 1;
  23. 	}
  24. };
  25.  
  26. void show_simplex(vector<vector<fract> >fra){
  27. 	for(int i=0;i<fra.size();i++){
  28. 		for(int j=0;j<fra[0].size();j++){
  29. 			printf("%4d/%-4d ",fra[i][j].bunsi,fra[i][j].bunbo);
  30. 		}
  31. 		cout << endl;
  32. 	}
  33. 	cout << endl;
  34. }
  35.  
  36. int judge(vector<vector<fract> > simplex){
  37. 	for(int i=1;i<simplex[0].size();i++){
  38. 		if(simplex[0][i].bunbo*simplex[0][i].bunsi > 0){
  39. 			return i;
  40. 		}
  41. 	}
  42. 	return -1;
  43. }
  44.  
  45. int gcd(int a, int b) {
  46. 	int c;
  47. 	while (a != 0) {
  48. 		c = a;
  49. 		a = b % a;
  50. 		b = c;
  51. 	}
  52. 	return b;
  53. }
  54.  
  55. vector<vector<fract> > yakubun(vector<vector<fract> > fra){
  56. 	for(int i=0;i<fra.size();i++){
  57. 		for(int j=0;j<fra[0].size();j++){
  58. 			fract tmp = fra[i][j];
  59. 			int a = gcd(abs(tmp.bunsi),abs(tmp.bunbo));
  60. 			fra[i][j].bunsi = (fra[i][j].bunsi / a) * (fra[i][j].bunbo/abs(fra[i][j].bunbo));
  61. 			fra[i][j].bunbo = abs(fra[i][j].bunbo) / a;
  62. 		}
  63. 	}
  64. 	return fra;
  65. }
  66.  
  67. double act(fract a){
  68. 	if(a.bunbo == 0)return INF;
  69. 	return (double)a.bunsi/a.bunbo;
  70. }
  71.  
  72. int stoi(string s){
  73. 	int ret =0;
  74. 	bool fu = false;
  75. 	for(int i=0;i<s.size();i++){
  76. 		if(s[i]=='-'){
  77. 			fu = true;
  78. 			continue;
  79. 		}
  80. 		ret *= 10;
  81. 		ret += (s[i] - '0');
  82. 	}
  83. 	return ret * (fu ? -1 : 1);
  84. }
  85.  
  86. int main(void){
  87. 	int N,M;
  88. 	cin >> N >> M;// >> surplus;
  89. 	vector<vector<fract> >simplex(N);
  90. 	for(int i=0;i<N;i++){
  91. 		for(int j=0;j<M;j++){
  92. 			string s;
  93. 			cin >> s;
  94. 			fract fra;
  95. 			int n;
  96. 			if((n=s.find('/'))==-1){
  97. 				fra.bunsi = stoi(s);
  98. 				simplex[i].push_back(fra);
  99. 			}else{
  100. 				fra.bunsi = stoi(s.substr(0,n));
  101. 				fra.bunbo = stoi(s.substr(n+1));
  102. 				simplex[i].push_back(fra);
  103. 			}
  104. 		}
  105. 	}
  106. 	show_simplex(simplex);
  107. 	//列を決定
  108. 	int c = 1;
  109. 	while((c = judge(simplex)) != -1 ){
  110. 		//行を決定
  111. 		fract tmp2;
  112. 		int r = -1;
  113. 		double sa = INF;
  114. 		for(int i=1;i<N;i++){ //todo 2段階なら、1->2
  115. 			fract tmp = simplex[i][c];
  116. 			fract hidari = simplex[i][0];
  117. 			if(tmp.bunsi <= 0 || hidari.bunsi <= 0)continue;
  118. 			if(r==-1){
  119. 				sa = act(hidari)/act(tmp);
  120. 				r=i;
  121. 			}
  122. 			else if(act(hidari)/act(tmp) < sa){
  123. 				sa = act(hidari)/act(tmp);
  124. 				r = i;
  125. 			}
  126. 		}
  127. 		cout << r << "," << c << endl;
  128. 		if(r<0)return 0;
  129. 		//注目箇所を１に合わせるように逆数をかける
  130. 		fract rec(abs(simplex[r][c].bunsi),simplex[r][c].bunbo*abs(simplex[r][c].bunsi)/simplex[r][c].bunsi);
  131. 		for(int i=0;i<M;i++){
  132. 			simplex[r][i].bunbo *= rec.bunbo;
  133. 			simplex[r][i].bunsi *= rec.bunsi;
  134. 		}
  135. 		simplex = yakubun(simplex);
  136. 		fract power;
  137. 		for(int i=0;i<N;i++){
  138. 			if(r == i)continue;
  139. 			power = simplex[i][c];
  140. 			for(int j=0;j<M;j++){
  141. 				simplex[i][j].bunsi = 	simplex[r][j].bunbo*simplex[i][j].bunsi*power.bunbo -
  142. 						simplex[r][j].bunsi*simplex[i][j].bunbo*power.bunsi;
  143. 				simplex[i][j].bunbo *=  simplex[r][j].bunbo * power.bunbo;
  144. 			}
  145. 		}
  146. 		simplex = yakubun(simplex);
  147. 		show_simplex(simplex);
  148. 		cout << endl;
  149. 	}
  150. 	cout << "Answer =" << simplex[0][0].bunsi << "/" << simplex[0][0].bunbo << endl;
  151. 	show_simplex(simplex);
  152. 	return 0;
  153. }
  154.  
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
4 9
0 1 1 1 1 -1 0 0 0
7 13 16 17 15 2 1 0 0
8 13 10 9 17 5 0 1 0
2 14 2 5 8 4 0 0 1
stdout
copy 
   0/1       1/1       1/1       1/1       1/1      -1/1       0/1       0/1       0/1    
   7/1      13/1      16/1      17/1      15/1       2/1       1/1       0/1       0/1    
   8/1      13/1      10/1       9/1      17/1       5/1       0/1       1/1       0/1    
   2/1      14/1       2/1       5/1       8/1       4/1       0/1       0/1       1/1    

3,1
  -1/7       0/1       6/7       9/14      3/7      -9/7       0/1       0/1      -1/14   
  36/7       0/1      99/7     173/14     53/7     -12/7       1/1       0/1     -13/14   
  43/7       0/1      57/7      61/14     67/7       9/7       0/1       1/1     -13/14   
   1/7       1/1       1/7       5/14      4/7       2/7       0/1       0/1       1/14   


1,2
  -5/11      0/1       0/1      -7/66     -1/33    -13/11     -2/33      0/1      -1/66   
   4/11      0/1       1/1     173/198    53/99     -4/33      7/99      0/1     -13/198  
  35/11      0/1       0/1     -91/33    172/33     25/11    -19/33      1/1     -13/33   
   1/11      1/1       0/1      23/99     49/99     10/33     -1/99      0/1       8/99   


Answer =-5/11
  -5/11      0/1       0/1      -7/66     -1/33    -13/11     -2/33      0/1      -1/66   
   4/11      0/1       1/1     173/198    53/99     -4/33      7/99      0/1     -13/198  
  35/11      0/1       0/1     -91/33    172/33     25/11    -19/33      1/1     -13/33   
   1/11      1/1       0/1      23/99     49/99     10/33     -1/99      0/1       8/99
https://ideone.com/G58Cxh
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!