SHARE
TWEET

Untitled

a guest Mar 19th, 2011 150 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <map>
  9. #include <algorithm>
  10. #include <set>
  11. #include <cstdio>
  12. #include <cstring>
  13. #include <cstdlib>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <fstream>
  17. #include <numeric>
  18. #include <limits.h>
  19.  
  20. using namespace std;
  21.  
  22. typedef vector<int> vi;
  23. typedef vector<string> vs;
  24. typedef pair<int,int> ii;
  25. typedef long long ll;
  26.  
  27. #define ITE(v) typeof(v.begin())
  28. #define FOR(i,n) for(int i = 0; i < n; i++)
  29. #define FORIT(it,v) for(ITE(v) it = v.begin(); it != v.end(); it++)
  30. #define ALL(v) v.begin(), v.end()
  31. #define SZ(v) int(v.size())
  32. #define pb push_back
  33. #define SQR(a) ((a)*(a))
  34.  
  35. #define INF 0x3f3f3f3f
  36. #define EPS (1e-9)
  37.  
  38. inline int cmp(double a, double b = 0.0) {
  39.   if (fabs(a-b) <= EPS) return 0;
  40.   if (a < b) return -1;
  41.   return 1;
  42. }
  43.  
  44. #define MAX 7
  45.  
  46. int n;
  47.  
  48. int minf[MAX][MAX], maxf[MAX][MAX], cost[MAX][MAX];
  49. vi sol;
  50. int fs, cs;
  51.  
  52. map<vi,int> m;
  53.  
  54. int solve() {
  55.   if (sol[0] == n-1) return 0;
  56.   if (m.count(sol)) return m[sol];
  57.   int &r = m[sol];
  58.   r = -INF;
  59.   int v = sol[0];
  60.   int u = sol[1];
  61.   if (u == n) {
  62.     if (sol[v+2] > 0) return r = -INF;
  63.     sol[0] = v+1;
  64.     sol[1] = v+2;
  65.     r = solve();
  66.     sol[0] = v;
  67.     sol[1] = n;
  68.     return r;
  69.   }
  70.   if (sol[v+2] < minf[v][u]) return r = -INF;
  71.   for (int i = minf[v][u]; i <= min(sol[v+2],maxf[v][u]); i++) {
  72.     int c = i*i;
  73.     if (i > 0) c += cost[v][u];
  74.     sol[v+2] -= i;
  75.     sol[1]++;
  76.     sol[u+2] += i;
  77.     int rs = solve();
  78.     if (rs > -INF) r = max(r,rs+c);
  79.     sol[1]--;
  80.     sol[u+2] -= i;
  81.     sol[v+2] += i;
  82.   }
  83.   return r;
  84. }
  85.  
  86. int main() {
  87.   fs = 100;
  88.   cs = 0;
  89.   sol = vi(8);
  90.   cin >> n;
  91.   FOR(i,n*(n-1)/2) {
  92.     int s,f,l,h,a;
  93.     cin >> s >> f >> l >> h >> a;
  94.     s--;f--;
  95.     minf[s][f] = l;
  96.     maxf[s][f] = h;
  97.     cost[s][f] = a;
  98.   }
  99.   for (int i = 0; i <= 25; i++) {
  100.     sol[1] = 1;
  101.     sol[2] = i;
  102.     m.clear();
  103.     int r = solve();
  104.     if (r >= 0) {
  105.       cout << i << " " << r << endl;
  106.       return 0;
  107.     }    
  108.   }
  109.   cout << -1 << " " << -1 << endl;
  110.   return 0;
  111. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top