fork download
copy 
  1. // #define _CRT_SECURE_NO_WARNINGS 
  2.  
  3. #include <iostream> 
  4. #include <algorithm> 
  5. #include <cmath> 
  6. #include <climits> 
  7. #include <vector> 
  8. #include <queue> 
  9. #include <deque> 
  10. #include <array> 
  11. #include <list> 
  12. #include <stack> 
  13. #include <tuple> 
  14. #include <set> 
  15. #include <unordered_set> 
  16. #include <map> 
  17. #include <unordered_map> 
  18. #include <string> 
  19. #include <cstring> 
  20. #include <random> 
  21. #include <bitset> 
  22. #include <iomanip> 
  23. #include <iterator> 
  24. #include <functional> 
  25. #include <ctime> 
  26. #include <chrono> 
  27. #include <cctype> 
  28. #include <fstream> 
  29. #include <numeric> 
  30. #include <complex> 
  31. #include <cassert> 
  32.  
  33. using namespace std;
  34.  
  35. // #pragma GCC optimize("Ofast")
  36. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  37.  
  38. #define int               long long 
  39. #define sz(x)             ((int)(x).size()) 
  40. #define mp                make_pair 
  41. #define all(x)            (x).begin(), (x).end() 
  42. #define pb                push_back 
  43. #define pf                push_front 
  44. #define ff                first 
  45. #define ss                second 
  46. #define unique(x)         (x).erase(unique(all(x)), (x).end()) 
  47. #define min3(a, b, c)     min(a, min(b, c)) 
  48. #define max3(a, b, c)     max(a, max(b, c)) 
  49. #define FOR(i, a, b)      for (int i = (a); i <= (b); i++) 
  50. #define ROF(i, a, b)      for (int i = (a); i >= (b); i--) 
  51.  
  52. using vi = vector<int>;
  53. using vd = vector<double>;
  54. using vpii = vector<pair<int, int>>;
  55. using vpdd = vector<pair<double, double>>;
  56. using pii = pair<int, int>;
  57. using pdd = pair<double, double>;
  58.  
  59. // #include <ext/pb_ds/assoc_container.hpp>
  60. // #include <ext/pb_ds/tree_policy.hpp>
  61. // using namespace __gnu_pbds;
  62. // typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  63.  
  64. template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
  65. template<typename T> using max_heap = priority_queue<T>;
  66.  
  67. #define BIT(n) (1LL << (n))
  68. #define HAS_BIT(x, n) (((x) >> (n)) & 1)
  69. #define SET_BIT(x, n) ((x) | BIT(n))
  70.  
  71. template <typename Container>
  72. void PRINT(const Container& container) {
  73.     for (const auto& e : container) {
  74.         cout << e << ' ';
  75.     } cout << '\n';
  76. }
  77.  
  78. void print_double(double ans, int num) {
  79.     cout << fixed << setprecision(num) << ans << '\n';
  80. }
  81.  
  82. const int inf = 1e18;
  83. const double eps = 1e-9;
  84. const double PI = 3.141592653589793;
  85.  
  86. string alh = "abcdefghijklmnopqrstuvwxyz";
  87. string ALH = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  88.  
  89. class TP {
  90. private:
  91.     vector<vector<int>> c;
  92.     vector<int> s;
  93.     vector<int> d;
  94.     int m, n;
  95.  
  96.     vector<pair<int, int>> findCyc(vector<vector<int>>& sol, int si, int sj) {
  97.         int tot = m + n;
  98.         vector<int> par(tot, -1);
  99.         vector<bool> vis(tot, false);
  100.         queue<int> q;
  101.  
  102.         vis[si] = true;
  103.         q.push(si);
  104.         int tar = sj + m;
  105.  
  106.         while (!q.empty()) {
  107.             int node = q.front();
  108.             q.pop();
  109.  
  110.             if (node < m) {
  111.                 int i = node;
  112.                 for (int j = 0; j < n; j++) {
  113.                     if (sol[i][j] > 0) {
  114.                         int cn = j + m;
  115.                         if (!vis[cn]) {
  116.                             vis[cn] = true;
  117.                             par[cn] = node;
  118.                             q.push(cn);
  119.                             if (cn == tar) {
  120.                                 vector<int> path;
  121.                                 int cur = cn;
  122.                                 while (cur != -1) {
  123.                                     path.push_back(cur);
  124.                                     cur = par[cur];
  125.                                 }
  126.                                 reverse(path.begin(), path.end());
  127.  
  128.                                 vector<pair<int, int>> cyc;
  129.                                 cyc.push_back({ si, sj });
  130.  
  131.                                 for (int idx = 0; idx < path.size() - 1; idx++) {
  132.                                     int n1 = path[idx];
  133.                                     int n2 = path[idx + 1];
  134.                                     if (n1 < m && n2 >= m) {
  135.                                         cyc.push_back({ n1, n2 - m });
  136.                                     }
  137.                                     else if (n1 >= m && n2 < m) {
  138.                                         cyc.push_back({ n2, n1 - m });
  139.                                     }
  140.                                 }
  141.                                 return cyc;
  142.                             }
  143.                         }
  144.                     }
  145.                 }
  146.             }
  147.             else {
  148.                 int j = node - m;
  149.                 for (int i = 0; i < m; i++) {
  150.                     if (sol[i][j] > 0) {
  151.                         int rn = i;
  152.                         if (!vis[rn]) {
  153.                             vis[rn] = true;
  154.                             par[rn] = node;
  155.                             q.push(rn);
  156.                         }
  157.                     }
  158.                 }
  159.             }
  160.         }
  161.         return {};
  162.     }
  163.  
  164.     void redist(vector<vector<int>>& sol, vector<pair<int, int>>& cyc) {
  165.         if (cyc.size() < 4) return;
  166.  
  167.         int theta = INT_MAX;
  168.         for (int i = 1; i < cyc.size(); i += 2) {
  169.             int x = cyc[i].first, y = cyc[i].second;
  170.             if (sol[x][y] < theta) {
  171.                 theta = sol[x][y];
  172.             }
  173.         }
  174.  
  175.         for (int i = 0; i < cyc.size(); i++) {
  176.             int x = cyc[i].first, y = cyc[i].second;
  177.             if (i % 2 == 0) {
  178.                 sol[x][y] += theta;
  179.             }
  180.             else {
  181.                 sol[x][y] -= theta;
  182.             }
  183.         }
  184.     }
  185.  
  186. public:
  187.     TP(vector<vector<int>> c, vector<int> s, vector<int> d)
  188.         : c(c), s(s), d(d) {
  189.         m = s.size();
  190.         n = d.size();
  191.     }
  192.  
  193.     vector<vector<int>> NW() {
  194.         vector<vector<int>> sol(m, vector<int>(n, 0));
  195.         vector<int> sup = s, dem = d;
  196.         int i = 0, j = 0;
  197.  
  198.         while (i < m && j < n) {
  199.             int amt = min(sup[i], dem[j]);
  200.             sol[i][j] = amt;
  201.             sup[i] -= amt;
  202.             dem[j] -= amt;
  203.  
  204.             if (sup[i] == 0) i++;
  205.             if (dem[j] == 0) j++;
  206.         }
  207.         return sol;
  208.     }
  209.  
  210.     vector<vector<int>> solve() {
  211.         auto sol = NW();
  212.         int iter = 0;
  213.         const int MAX_ITER = 100;
  214.  
  215.         while (iter++ < MAX_ITER) {
  216.             vector<int> u(m, INT_MAX), v(n, INT_MAX);
  217.             u[0] = 0;
  218.  
  219.             bool ch;
  220.             do {
  221.                 ch = false;
  222.                 for (int i = 0; i < m; i++) {
  223.                     for (int j = 0; j < n; j++) {
  224.                         if (sol[i][j] > 0) {
  225.                             if (u[i] != INT_MAX && v[j] == INT_MAX) {
  226.                                 v[j] = c[i][j] - u[i];
  227.                                 ch = true;
  228.                             }
  229.                             else if (v[j] != INT_MAX && u[i] == INT_MAX) {
  230.                                 u[i] = c[i][j] - v[j];
  231.                                 ch = true;
  232.                             }
  233.                         }
  234.                     }
  235.                 }
  236.             } while (ch);
  237.  
  238.             int minD = 0;
  239.             int bestI = -1, bestJ = -1;
  240.  
  241.             for (int i = 0; i < m; i++) {
  242.                 for (int j = 0; j < n; j++) {
  243.                     if (sol[i][j] == 0) {
  244.                         if (u[i] == INT_MAX || v[j] == INT_MAX) continue;
  245.                         int delta = c[i][j] - (u[i] + v[j]);
  246.                         if (delta < minD) {
  247.                             minD = delta;
  248.                             bestI = i;
  249.                             bestJ = j;
  250.                         }
  251.                     }
  252.                 }
  253.             }
  254.  
  255.             if (minD >= 0) break;
  256.  
  257.             auto cyc = findCyc(sol, bestI, bestJ);
  258.             if (cyc.empty()) {
  259.                 cout << "Cycle not found for cell (" << bestI << "," << bestJ << ")" << endl;
  260.                 break;
  261.             }
  262.  
  263.             redist(sol, cyc);
  264.         }
  265.  
  266.         return sol;
  267.     }
  268.  
  269.     int calcCost(const vector<vector<int>>& sol) {
  270.         int tot = 0;
  271.         for (int i = 0; i < m; i++) {
  272.             for (int j = 0; j < n; j++) {
  273.                 tot += sol[i][j] * c[i][j];
  274.             }
  275.         }
  276.         return tot;
  277.     }
  278.  
  279.     void printSol(const vector<vector<int>>& sol) {
  280.         cout << "    ";
  281.         for (int j = 0; j < n; j++) cout << setw(3) << "B" << j + 1;
  282.         cout << setw(6) << "Sup" << endl;
  283.  
  284.         for (int i = 0; i < m; i++) {
  285.             cout << "A" << i + 1 << "  ";
  286.             int rs = 0;
  287.             for (int j = 0; j < n; j++) {
  288.                 cout << setw(4) << sol[i][j];
  289.                 rs += sol[i][j];
  290.             }
  291.             cout << setw(6) << rs << endl;
  292.         }
  293.  
  294.         cout << "Dem ";
  295.         for (int j = 0; j < n; j++) {
  296.             int cs = 0;
  297.             for (int i = 0; i < m; i++) {
  298.                 cs += sol[i][j];
  299.             }
  300.             cout << setw(4) << cs;
  301.         }
  302.         cout << endl;
  303.     }
  304. };
  305.  
  306. void Solve() {
  307.     vector<int> s = { 120, 90, 150 };
  308.     vector<int> d = { 50, 60, 40, 70, 30, 20, 90 };
  309.     vector<vector<int>> c = {
  310.         {4, 7, 2, 5, 8, 3, 6},
  311.         {9, 1, 6, 4, 2, 7, 5},
  312.         {3, 8, 5, 9, 1, 4, 2}
  313.     };
  314.  
  315.     TP tp(c, s, d);
  316.  
  317.     auto nw = tp.NW();
  318.     int nwCost = tp.calcCost(nw);
  319.     cout << "North-West corner cost: " << nwCost << endl;
  320.  
  321.     auto opt = tp.solve();
  322.     int optCost = tp.calcCost(opt);
  323.     cout << "Optimal solution cost: " << optCost << endl;
  324.  
  325.     tp.printSol(opt);
  326.  
  327.     bool ok = true;
  328.     for (int i = 0; i < s.size(); i++) {
  329.         int rs = 0;
  330.         for (int j = 0; j < d.size(); j++) {
  331.             rs += opt[i][j];
  332.         }
  333.         if (rs != s[i]) {
  334.             cout << "R " << i << " error: " << rs << " != " << s[i] << endl;
  335.             ok = false;
  336.         }
  337.     }
  338.  
  339.     for (int j = 0; j < d.size(); j++) {
  340.         int cs = 0;
  341.         for (int i = 0; i < s.size(); i++) {
  342.             cs += opt[i][j];
  343.         }
  344.         if (cs != d[j]) {
  345.             cout << "C " << j << " error: " << cs << " != " << d[j] << endl;
  346.             ok = false;
  347.         }
  348.     }
  349. }
  350.  
  351. signed main() {
  352.     ios_base::sync_with_stdio(false);
  353.     cin.tie(0);
  354.     cout.tie(0);
  355.  
  356.     /*
  357.                       ________________
  358.                      / Just solved it \
  359.                      |   in my mind   |
  360.                      \________________/
  361.                     /
  362.                    /
  363. 　　　　　／＞　 フ         ___________
  364. 　　　　　| 　_　 _|       |          |
  365. 　 　　　／`ミ _x 彡       |   WA 2   |
  366. 　　 　 /　　　 　 |       |__________|
  367. 　　　 /　 ヽ　　 ﾉ        /          /
  368. 　／￣|　　 |　|　|       /_________ /
  369. 　| (￣ヽ＿_ヽ_)_)
  370. 　＼二つ
  371.  
  372.     */
  373.  
  374.     /*
  375.     freopen("task.in", "r", stdin);
  376.     freopen("task.out", "w", stdout);
  377.     */
  378.  
  379.     // auto start = chrono::high_resolution_clock::now();
  380.  
  381.     int multitest = false;
  382.     if (multitest == true) {
  383.         int ctt; cin >> ctt;
  384.  
  385.         for (int i = 0; i < ctt; i++) {
  386.             Solve();
  387.         }
  388.     }
  389.     else {
  390.         Solve();
  391.     }
  392.  
  393.     // auto end = chrono::high_resolution_clock::now();
  394.  
  395.     /*
  396.     cout << "Time taken: "
  397.          << chrono::duration_cast<chrono::milliseconds>(end - start).count()
  398.          << " milliseconds" << endl;
  399.     */
  400.  
  401.     return 0;
  402. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
North-West corner cost: 1440
Optimal solution cost: 900
      B1  B2  B3  B4  B5  B6  B7   Sup
A1    20   0  40  40   0  20   0   120
A2     0  60   0  30   0   0   0    90
A3    30   0   0   0  30   0  90   150
Dem   50  60  40  70  30  20  90
https://ideone.com/2IMo8r
language:
C++ (gcc 8.3)
created:
9 hours 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!