fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long double DOUBLE;
  6. typedef vector<DOUBLE> VD;
  7. typedef vector<VD> VVD;
  8. typedef vector<int> VI;
  9.  
  10. const DOUBLE EPS = 1e-9;
  11.  
  12. struct LPSolver {
  13. int m, n;
  14. VI B, N;
  15. VVD D;
  16.  
  17. LPSolver(const VVD &A, const VD &b, const VD &c) :
  18. m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
  19. for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
  20. for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
  21. for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
  22. N[n] = -1; D[m + 1][n] = 1;
  23. }
  24.  
  25. void Pivot(int r, int s) {
  26. for (int i = 0; i < m + 2; i++) if (i != r)
  27. for (int j = 0; j < n + 2; j++) if (j != s)
  28. D[i][j] -= D[r][j] * D[i][s] / D[r][s];
  29. for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] /= D[r][s];
  30. for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] /= -D[r][s];
  31. D[r][s] = 1.0 / D[r][s];
  32. swap(B[r], N[s]);
  33. }
  34.  
  35. bool Simplex(int phase) {
  36. int x = phase == 1 ? m + 1 : m;
  37. while (true) {
  38. int s = -1;
  39. for (int j = 0; j <= n; j++) {
  40. if (phase == 2 && N[j] == -1) continue;
  41. if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
  42. }
  43. if (D[x][s] > -EPS) return true;
  44. int r = -1;
  45. for (int i = 0; i < m; i++) {
  46. if (D[i][s] < EPS) continue;
  47. if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
  48. (D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r]) r = i;
  49. }
  50. if (r == -1) return false;
  51. Pivot(r, s);
  52. }
  53. }
  54.  
  55. DOUBLE Solve(VD &x) {
  56. int r = 0;
  57. for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
  58. if (D[r][n + 1] < -EPS) {
  59. Pivot(r, n);
  60. if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
  61. for (int i = 0; i < m; i++) if (B[i] == -1) {
  62. int s = -1;
  63. for (int j = 0; j <= n; j++)
  64. if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
  65. Pivot(i, s);
  66. }
  67. }
  68. if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
  69. x = VD(n);
  70. for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
  71. return D[m][n + 1];
  72. }
  73. };
  74.  
  75. int n;
  76. vector<int> adj[50];
  77. int ideg[50];
  78. VD on;
  79. VVD equations;
  80. vector<int> sumtime;
  81. int sum;
  82. vector<int> Time, Cost;
  83.  
  84. void dfs(int u)
  85. {
  86. on[u]=-1.0;
  87. sum+=Time[u];
  88. if(adj[u].empty())
  89. {
  90. equations.push_back(on);
  91. sumtime.push_back(sum);
  92. }
  93. else
  94. for(auto& v: adj[u])
  95. dfs(v);
  96. sum-=Time[u];
  97. on[u]=0.0;
  98. }
  99.  
  100. #define PROBLEM Farmville
  101. class PROBLEM
  102. {
  103. public:
  104. #define METHOD minTime
  105. int minTime(vector <string> s, vector <int> time, vector <int> cost, int budget)
  106. {
  107. Time=time;
  108. Cost=cost;
  109. n=s.size();
  110. for(int i=0; i<n; i++)
  111. for(int j=0; j<n; j++)
  112. if(s[i][j]=='1')
  113. adj[j].push_back(i), ideg[i]++;
  114. on.resize(n);
  115. for(int i=0; i<n; i++) if(ideg[i]==0)
  116. dfs(i);
  117. VD constraint;
  118. for(int i=0; i<n; i++)
  119. constraint.push_back(-Cost[i]);
  120. int m=equations.size();
  121. int lo=0, mid, hi=25*50;
  122. VD b(m);
  123. for(int i=0; i<n; i++)
  124. {
  125. VD v(n, 0.0);
  126. v[i]=1.0;
  127. equations.push_back(v);
  128. b.push_back(Time[i]);
  129. }
  130. while(lo<hi)
  131. {
  132. mid=(lo+hi)/2;
  133. for(int i=0; i<m; i++)
  134. b[i]=-(sumtime[i]-mid);
  135. LPSolver slv(equations, b, constraint);
  136. VD x;
  137. double ans=-slv.Solve(x);
  138. if(ans<=budget)
  139. hi=mid;
  140. else
  141. lo=mid+1;
  142. }
  143. return lo;
  144. }
  145. };
  146.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
Standard output is empty