fork download
copy 
  1. #pragma GCC optimize ("O3")
  2. #include <bits/stdc++.h>
  3. #define loop(i,n) for(int i = 0;i < (n);i++)
  4. #define all(A) A.begin(),A.end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define sz(A) ((int)A.size())
  8. typedef std::vector<int> vi;
  9. typedef std::pair<int,int> pi;
  10. typedef std::vector<pi> vp;
  11. typedef long long ll;
  12. #define popcnt(x) __builtin_popcount(x)
  13. #define LSOne(x) ((x) & (-(x)))
  14. #define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
  15. #define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
  16. #define PRESTDIO() cin.tie(0),cerr.tie(0),ios_base::sync_with_stdio(0)
  17. #define what_is(x) cerr << #x << " is " << x << endl
  18. #define bit_lg(x) (assert(x > 0),__builtin_ffsll(x) - 1)
  19. const double PI = acos(-1);
  20. template<class A,class B>
  21. std::ostream& operator << (std::ostream& st,const std::pair<A,B> p) {
  22. 	st << "(" << p.first << ", " << p.second << ")";
  23. 	return st;
  24. }
  25. using namespace std;
  26.  
  27.  
  28. using ld = long double;
  29. using row = vector<ld>;
  30. using matrix = vector<row>;
  31. const ld eps = 1e-12;
  32.  
  33. ostream& operator << (ostream& os, const matrix & A) {
  34. 	os << "[";
  35. 	bool firstRow = true;
  36. 	for(auto R : A){
  37. 		if(!firstRow) {
  38. 			os << "; ";
  39. 		}
  40. 		firstRow = false;
  41. 		bool firstItem = true;
  42. 		for(auto x : R) {
  43. 			if(!firstItem) os << " ";
  44. 			os << x;
  45. 			firstItem = false;
  46. 		}
  47. 	}
  48. 	os << "]";
  49. 	return os;
  50. }
  51.  
  52. void gauss(matrix & A){
  53. 	int n = sz(A);
  54. 	loop(pivot, n){
  55. 		int r = -1;
  56. 		for(int i = pivot; i < n; i++) {
  57. 			if(abs(A[i][pivot]) > eps){
  58. 				r = i;
  59. 				break;
  60. 			}
  61. 		}
  62. 		assert(r != -1);
  63. 		if(r != pivot) A[pivot].swap(A[r]);
  64. 		ld s = A[pivot][pivot];
  65. 		for(auto & x : A[pivot]) x /= s;
  66. 		for(int i = pivot + 1; i < n; i++){
  67. 			s = A[i][pivot];
  68. 			for(int c = pivot; c < sz(A[i]); c++){
  69. 				A[i][c] -= s * A[pivot][c];
  70. 			}
  71. 		}
  72. 	}
  73. 	for(int pivot = n-1; pivot >= 0; pivot--){
  74. 		for(int r = pivot - 1; r >= 0; r--){
  75. 			ld s = A[r][pivot];
  76. 			for(int c = pivot; c < sz(A[r]); c++)
  77. 				A[r][c] -= s * A[pivot][c];
  78. 		}
  79. 	}
  80. }
  81.  
  82. void inv_matrix(matrix & A){
  83. 	int n = sz(A);
  84. 	loop(i, n){
  85. 		A[i].resize(2*n, 0);
  86. 		A[i][i + n] = 1;
  87. 	}
  88. 	gauss(A);
  89. 	loop(i, n){
  90. 		rotate(A[i].begin(), A[i].begin() + n, A[i].end());
  91. 		A[i].resize(n);
  92. 	}
  93. }
  94.  
  95.  
  96.  
  97.  
  98. vi V;
  99. vector<bool> vis;
  100. int n, m;
  101. vector<vp> G;
  102.  
  103. void dfs(int u){
  104. 	if(vis[u]) return;
  105. 	vis[u] = true;
  106. 	V.push_back(u);
  107. 	for(auto [v, _] : G[u]) dfs(v);
  108. }
  109.  
  110. void tc(){
  111. 	G.clear();
  112. 	G.resize(n);
  113. 	loop(e, m){
  114. 		int a, b, c; scanf("%d %d %d", &a, &b, &c);
  115. 		a--, b--;
  116. 		G[a].emplace_back(b, c);
  117. 		G[b].emplace_back(a, c);
  118. 	}
  119. 	if(n == 2){
  120. 		ld R = 0;
  121. 		for(auto [_, r] : G[0]){
  122. 			R += 1.0/r;
  123. 		}
  124. 		R = 1.0/R;
  125. 		printf("%.02f\n", (double)R);
  126. 		return;
  127. 	}
  128. 	V.clear();
  129. 	vis.resize(n);
  130. 	fill(all(vis), false);
  131. 	dfs(0);
  132. 	sort(all(V));
  133. 	assert(V.back() == n-1);
  134. 	int N = sz(V) - 2;
  135. 	matrix A(N, row(N, 0.0));
  136. 	row B(N, 0.0);
  137. 	loop(i, N){
  138. 		int u = V[i + 1];
  139. 		ld scaler = 0;
  140. 		for(auto [v, r] : G[u]){
  141. 			if(v == 0 || v == n-1){
  142. 				B[i] += (v == 0)/(ld)r;
  143. 			} else {
  144. 				A[i][lower_bound(all(V), v) - V.begin() - 1] += 1.0/r;
  145. 			}
  146. 			scaler += 1.0/r;
  147. 		}
  148. 		for(auto & x : A[i]) x /= scaler;
  149. 		B[i] /= scaler;
  150. 	}
  151. 	loop(i, N) loop(j, N) A[i][j] = (i == j) - A[i][j];
  152. 	inv_matrix(A);
  153. 	row Volt(N, 0.0);
  154. 	loop(i, N) loop(j, N) Volt[i] += A[i][j] * B[j];
  155. 	ld current = 0;
  156. 	for(auto [v, r] : G[0]){
  157. 		if(v == n-1){
  158. 			current += 1.0/r;
  159. 		} else {
  160. 			int j = lower_bound(all(V), v) - V.begin() - 1;
  161. 			ld dv = 1 - Volt[j];
  162. 			current += dv / r;			
  163. 		}
  164. 	}
  165. 	ld resistance = 1.0/current;
  166. 	printf("%.2f\n", (double)resistance);
  167. }
  168.  
  169.  
  170.  
  171. int main(){
  172. #ifdef HOME
  173. 	freopen("in.in", "r", stdin);
  174. #endif
  175. 	while(scanf("%d %d", &n, &m) == 2) tc();
  176. 	return 0;
  177. }
  178.  
Success #stdin #stdout 0s 4744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lzYvjn
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!