fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/knlGNZ
language:
C++14 (gcc 8.3)
created:
9 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!