Facebook

Untitled

From Voluminous Plover, 5 Months ago, written in C++.
URL http://pastebin.pl/view/ad0c733d
Embed
Download Paste or View Raw
Hits: 102
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Edge {
  6.     long long int to;
  7.     long long int flow;
  8.     long long int cap;
  9.     long long int index;
  10.  
  11.     Edge(long long int to, long long int flow, long long int cap, long long int index) : to(to), flow(flow), cap(cap), index(index) {}
  12.  
  13.     bool isAvailable() {
  14.         return cap > flow;
  15.     }
  16.  
  17.     long long int getResidue() {
  18.         return cap - flow;
  19.     }
  20. };
  21.  
  22. class Flow {
  23. private:
  24.     long long int V, E, S, T;
  25.     long long int *excess;
  26.     long long int *height;
  27.     vector<Edge> *graph;
  28.     queue<long long int> active;
  29.     long long int *positionInAdj;
  30.     long long int counter;
  31.  
  32.  
  33. public:
  34.     Flow(long long int V, long long int E) {
  35.         Flow::V = V;
  36.         Flow::E = E;
  37.         Flow::graph = new vector<Edge>[Flow::V + 1];
  38.         Flow::excess = new long long int[Flow::V + 1];
  39.         Flow::height = new long long int[Flow::V + 1];
  40.         Flow::positionInAdj = new long long int[Flow::V + 1];
  41.         counter = 0;
  42.     }
  43.  
  44.     virtual ~Flow() {
  45.         delete[] Flow::graph;
  46.         delete[] Flow::excess;
  47.         delete[] Flow::height;
  48.         delete[] Flow::positionInAdj;
  49.     }
  50.  
  51.     void addEdge(long long int from, long long int to, long long int cap);
  52.  
  53.     void setSource(long long int S);
  54.  
  55.     void setSink(long long int T);
  56.  
  57.     void clearPositionInAdj();
  58.  
  59.     long long int getFlow();
  60.  
  61.     void bfs(long long int start);
  62.  
  63.     void preFlow();
  64.  
  65.     void relabel(long long int u);
  66.  
  67.     void discharge(long long int u);
  68.  
  69.     void push(long long int u, Edge &edge);
  70.  
  71.     void globalRelabeling();
  72. };
  73.  
  74. void Flow::addEdge(long long int from, long long int to, long long int cap) {
  75.     Edge edgeOne(to, 0, cap, (long long int) graph[to].size());
  76.     Edge edgeTwo(from, 0, 0, (long long int) graph[from].size());
  77.  
  78.     graph[from].push_back(edgeOne);
  79.     graph[to].push_back(edgeTwo);
  80. }
  81.  
  82. void Flow::setSource(long long int S) {
  83.     Flow::S = S;
  84. }
  85.  
  86. void Flow::setSink(long long int T) {
  87.     Flow::T = T;
  88. }
  89.  
  90. void Flow::clearPositionInAdj() {
  91.     for (long long int i = 1; i <= Flow::V; i++) {
  92.         Flow::positionInAdj[i] = 0;
  93.     }
  94. }
  95.  
  96. void Flow::bfs(long long int start) {
  97.     Flow::height[start] = Flow::V * (start == Flow::S);
  98.  
  99.     queue<long long int> temp;
  100.     temp.push(start);
  101.  
  102.     while (!temp.empty()) {
  103.         long long int r = temp.front();
  104.         temp.pop();
  105.         for (auto &v : graph[r]) {
  106.             Edge backward = graph[v.to][v.index];
  107.             if (Flow::height[v.to] == 2 * Flow::V && backward.isAvailable()) {
  108.                 Flow::height[v.to] = Flow::height[r] + 1;
  109.                 temp.push(v.to);
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. long long int Flow::getFlow() {
  116.     Flow::clearPositionInAdj();
  117.  
  118.     for (long long int i = 1; i <= Flow::V; i++) {
  119.         Flow::height[i] = 0;
  120.     }
  121.  
  122.     Flow::height[S] = V;
  123.     Flow::preFlow();
  124.  
  125.     while (!active.empty()) {
  126.         long long int current = Flow::active.front();
  127.         Flow::active.pop();
  128.         Flow::discharge(current);
  129.     }
  130.  
  131.     return Flow::excess[Flow::T];
  132. }
  133.  
  134. void Flow::preFlow() {
  135.     for (long long int i = 1; i <= Flow::V; i++) {
  136.         Flow::excess[i] = 0;
  137.     }
  138.  
  139.     Flow::excess[Flow::S] = LONG_LONG_MAX;
  140.  
  141.     for (auto &v : graph[Flow::S]) {
  142.         Flow::push(Flow::S, v);
  143.  
  144.         if (v.to != Flow::T) {
  145.             Flow::active.push(v.to);
  146.         }
  147.     }
  148. }
  149.  
  150. void Flow::relabel(long long int u) {
  151.     Flow::height[u] = LONG_LONG_MAX;
  152.  
  153.     for (auto &v : graph[u]) {
  154.         if (v.isAvailable()) {
  155.             Flow::height[u] = min(Flow::height[u], Flow::height[v.to]);
  156.         }
  157.     }
  158.     Flow::height[u] += 1;
  159.     Flow::counter++;
  160.  
  161.     if (Flow::counter > Flow::V) {
  162.         Flow::globalRelabeling();
  163.         Flow::counter = 0;
  164.     }
  165. }
  166.  
  167. void Flow::push(long long int u, Edge &edge) {
  168.     long long int flow = min(Flow::excess[u], edge.getResidue());
  169.  
  170.     Flow::excess[u] -= flow;
  171.     Flow::excess[edge.to] += flow;
  172.     edge.flow += flow;
  173.     graph[edge.to][edge.index].flow -= flow;
  174. }
  175.  
  176. void Flow::discharge(long long int u) {
  177.     while (Flow::excess[u] > 0) {
  178.         if (Flow::positionInAdj[u] != graph[u].size()) {
  179.             if (graph[u][Flow::positionInAdj[u]].isAvailable() &&
  180.                 Flow::height[u] > Flow::height[graph[u][Flow::positionInAdj[u]].to]) {
  181.  
  182.                 long long int e = graph[u][Flow::positionInAdj[u]].to;
  183.                 Flow::push(u, graph[u][Flow::positionInAdj[u]]);
  184.  
  185.                 if (e != Flow::S && e != Flow::T) {
  186.                     Flow::active.push(e);
  187.                 }
  188.             } else {
  189.                 Flow::positionInAdj[u]++;
  190.             }
  191.         } else {
  192.             Flow::relabel(u);
  193.             Flow::active.push(u);
  194.             Flow::positionInAdj[u] = 0;
  195.         }
  196.     }
  197. }
  198.  
  199. void Flow::globalRelabeling() {
  200.     for (long long int i = 1; i <= Flow::V; i++) {
  201.         Flow::height[i] = 2 * Flow::V;
  202.     }
  203.  
  204.     Flow::bfs(Flow::T);
  205.     Flow::bfs(Flow::S);
  206. }
  207.  
  208. int main() {
  209.     ios_base::sync_with_stdio(false);
  210.  
  211.     long long int z;
  212.     cin >> z;
  213.  
  214.     while (z--) {
  215.         long long int n, m, s, t;
  216.         cin >> n >> m >> s >> t;
  217.  
  218.         Flow flow(n, m);
  219.         flow.setSource(s);
  220.         flow.setSink(t);
  221.  
  222.         map<pair<long long int, long long int>, long long int> edge;
  223.  
  224.         for (long long int i = 1; i <= m; i++) {
  225.             long long int a, b;
  226.             long long int c;
  227.             cin >> a >> b >> c;
  228.  
  229.             map<pair<long long int, long long int>, long long int>::iterator it = edge.find(make_pair(a, b));
  230.  
  231.             if (it != edge.end()) {
  232.                 it->second = it->second + c;
  233.             } else {
  234.                 edge[make_pair(a, b)] = c;
  235.             }
  236.         }
  237.  
  238.         for (map<pair<long long int, long long int>, long long int>::iterator it = edge.begin(); it != edge.end(); it++) {
  239.             flow.addEdge(it->first.first, it->first.second, it->second);
  240.         }
  241.  
  242.         cout << flow.getFlow() << endl;
  243.     }
  244.  
  245.     return 0;
  246. }

Reply to "Untitled"