fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int POCET_MIEST = 1000;
  5. const int ZDROJ = POCET_MIEST, ODTOK = POCET_MIEST+1;
  6. const long long NEKONECNO = 1LL << 60;
  7.  
  8. struct edge { 
  9.     int source, destination;
  10.     long long capacity, residue, cost;
  11.     edge(int s, int d, long long cap, long long res, long long cost) 
  12.         : source(s), destination(d), capacity(cap), residue(res), cost(cost) { }
  13. };
  14.  
  15. void add_arc(vector<edge> &edges, int source, int destination, long long capacity, long long cost) {
  16.     edges.push_back( edge(source,destination,capacity,capacity,cost) );
  17.     edges.push_back( edge(destination,source,capacity,0,-cost) );
  18. }
  19.  
  20. int main() {
  21.     vector<long long> mam_losov(POCET_MIEST);   for (auto &x : mam_losov)   cin >> x;
  22.     vector<long long> chcem_losov(POCET_MIEST); for (auto &x : chcem_losov) cin >> x;
  23.  
  24.     long long dokopy_losov = accumulate( mam_losov.begin(), mam_losov.end(), 0LL );
  25.  
  26.     vector<edge> edges;
  27.  
  28.     // hrany zo zdroja + hrany do odtoku
  29.     for (int i=0; i<POCET_MIEST; ++i) add_arc( edges, ZDROJ, i, mam_losov[i], 0 );
  30.     for (int i=0; i<POCET_MIEST; ++i) add_arc( edges, i, ODTOK, chcem_losov[i], 0 );
  31.  
  32.     // hrany medzi jednotlivymi mestami
  33.     for (int a=0; a<POCET_MIEST; ++a) for (int b=0; b<POCET_MIEST; ++b) {
  34.         long long c;
  35.         cin >> c;
  36.         if (a != b) add_arc( edges, a, b, dokopy_losov, c );
  37.     }
  38.  
  39.     // dokola zlepsujeme tok, az kym sa to uz niekedy neda
  40.     long long velkost_toku = 0, cena_toku = 0;
  41.  
  42.     while (true) {
  43.         // hladame najlacnejsiu zlepsujucu cestu algoritmom Bellmana a Forda
  44.         // (nie Dijkstra, lebo sice nemame zaporne cykly, ale mozeme mat zaporne hrany)
  45.         vector<long long> min_cena_cesty (POCET_MIEST+2, NEKONECNO);
  46.         vector<int> odkial(POCET_MIEST+2, -1);
  47.         min_cena_cesty[ZDROJ] = 0;
  48.         while (true) {
  49.             bool zmena = false;
  50.             for (unsigned i=0; i<edges.size(); ++i) {
  51.                 edge &e = edges[i];
  52.                 if (e.residue == 0) continue;
  53.                 if (min_cena_cesty[e.destination] > min_cena_cesty[e.source] + e.cost) {
  54.                     zmena = true;
  55.                     min_cena_cesty[e.destination] = min_cena_cesty[e.source] + e.cost;
  56.                     odkial[e.destination] = i;
  57.                 }
  58.             }
  59.             if (!zmena) break;
  60.         }
  61.  
  62.         // ak uz ziadna zlepsujuca cesta neexistovala, hotovo
  63.         if (min_cena_cesty[ODTOK] == NEKONECNO) break;
  64.  
  65.         // prejdeme po zlepsujucej ceste a zozbierame hrany ktore ju tvoria
  66.         vector<int> hrany_na_ceste;
  67.         {
  68.             int kde = ODTOK;
  69.             while (kde != ZDROJ) {
  70.                 hrany_na_ceste.push_back( odkial[kde] ); 
  71.                 kde = edges[odkial[kde]].source; 
  72.             }
  73.         }
  74.  
  75.         // zistime, o kolko vieme zlepsit tok
  76.         long long kapacita_cesty = NEKONECNO;
  77.         for (int h : hrany_na_ceste) kapacita_cesty = min( kapacita_cesty, edges[h].residue );
  78.  
  79.         // znova prejdeme po zlepsujucej ceste a upravime tok (aj na dualnych hranach)
  80.         velkost_toku += kapacita_cesty;
  81.         for (int h : hrany_na_ceste) {
  82.             cena_toku += kapacita_cesty * edges[h].cost;
  83.             edges[h].residue -= kapacita_cesty;
  84.             edges[h^1].residue += kapacita_cesty;
  85.         }
  86.     }
  87.     assert( velkost_toku == dokopy_losov );
  88.     cout << cena_toku << endl;
  89. }
Success #stdin #stdout 0.09s 68464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6osvht
language:
C++14 (gcc 8.3)
created:
6 years 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!