Advertisement
wrg0ababd

Untitled

Apr 20th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. struct edge {
  7.     int u, v, c, f, cost, num;
  8.  
  9.     edge(int from, int to, int cap, int cost, int num):u(from), v(to), c(cap), f(0), cost(cost), num(num){}
  10. };
  11.  
  12. int inf = 2e9;
  13. vector<edge> e;
  14. vector<vector<int>> g;
  15. vector<int> p;
  16. vector<int> dist;
  17. vector<char> used;
  18. int n, m, s, t;
  19. double before, after;
  20.  
  21. void print_edges() {
  22.     for (int i = 0; i < e.size(); i += 2) {
  23.         cout << e[i].u << ' ' << e[i].v << ' ' << e[i].f << ' ' << e[i].c << ' ' << e[i].cost << endl;
  24.     }
  25.     cout << "-------" << endl;
  26. }
  27.  
  28. int bfs(int maxc) {
  29.     dist.assign(n, inf);
  30.     queue<int> q;
  31.     q.push(s);
  32.     dist[s] = 0;
  33.     while (q.size() > 0) {
  34.         int v = q.front();
  35.         q.pop();
  36.         for (int i : g[v]) {
  37.             int to = e[i].v;
  38.             if (e[i].c - e[i].f < maxc) continue;
  39.             if (dist[to] == inf) {
  40.                 dist[to] = dist[v] + 1;
  41.                 q.push(to);
  42.             }
  43.         }
  44.     }
  45.     return dist[t];
  46. }
  47.  
  48. int dfs(int v, int minc, int maxc) {
  49.     if (used[v]) return 0;
  50.     used[v] = true;
  51.     if (v == t || minc == 0) {
  52.         return minc;
  53.     }
  54.     for (; p[v] < g[v].size(); p[v]++) {
  55.         int i = g[v][p[v]];
  56.         if (e[i].c - e[i].f < maxc || dist[e[i].v] != dist[v] + 1) continue;
  57.         int delta = dfs(e[i].v, min(minc, e[i].c - e[i].f), maxc);
  58.         if (delta > 0) {
  59.             e[i].f += delta;
  60.             e[i ^ 1].f -= delta;
  61.             return delta;
  62.         }
  63.     }
  64.     return 0;
  65. }
  66.  
  67. int dinic(int maxc, int need) {
  68.     int flow = 0;
  69.     while (bfs(maxc) != inf) {
  70.         p.assign(n, 0);
  71.         int added = 0;
  72.         do {
  73.             used.assign(n, false);
  74.             added = dfs(s, need, maxc);
  75.             flow += added;
  76.             need -= added;
  77.         } while (added > 0);
  78.         if (need == 0) {
  79.             break;
  80.         }
  81.     }
  82.     return flow;
  83. }
  84.  
  85. vector<double> price;
  86. vector<int> excess;
  87. deque<int> q;
  88. double eps = 1e6;
  89. double epsilon = 1e-8;
  90.  
  91. int relabels = 0;
  92. vector<char> prices_used;
  93. unordered_set<int> neg;
  94. unordered_set<int> vis;
  95.  
  96. void dfs_update(int u) {
  97.     prices_used[u] = true;
  98.     vis.insert(u);
  99.     for (int i : g[u]) {
  100.         int v = e[i].v;
  101.         if (e[i ^ 1].f == e[i ^ 1].c || e[i ^ 1].cost + price[v] - price[u] > 0) continue;
  102.         if (!prices_used[v]) {
  103.             dfs_update(v);
  104.         }
  105.     }
  106. }
  107.  
  108. void price_update() {
  109.     vis.clear();
  110.     for (int v : neg) {
  111.         if (!prices_used[v]) {
  112.             dfs_update(v);
  113.         }
  114.     }
  115.     for (int v : q) {
  116.         if (!prices_used[v] && !vis.count(v)) {
  117.             price[v] -= eps;
  118.         }
  119.     }
  120.     for (int v : vis) {
  121.         prices_used[v] = false;
  122.     }
  123. }
  124.  
  125. void push(int i) {
  126.     int u = e[i].u;
  127.     int v = e[i].v;
  128.     int delta = min(e[i].c - e[i].f, excess[u]);
  129.     e[i].f += delta;
  130.     e[i ^ 1].f -= delta;
  131.     excess[u] -= delta;
  132.     excess[v] += delta;
  133.     if (excess[v] - delta < 0 && excess[v] >= 0) {
  134.         neg.erase(i);
  135.     }
  136.     if (excess[v] > 0 && !used[v]) {
  137.         used[v] = true;
  138.         q.push_back(v);
  139.     }
  140. }
  141.  
  142. void relabel(int u) {
  143.     ++relabels;
  144.     double next = -1e18;
  145.     for (int i : g[u]) {
  146.         int v = e[i].v;
  147.         if (e[i].f < e[i].c) {
  148.             next = max(next, price[v] - e[i].cost - eps);
  149.         }
  150.     }
  151.     price[u] = next;
  152.     // price[u] -= eps;
  153. }
  154.  
  155. void discharge(int u) {
  156.     while (true) {
  157.         if (p[u] == g[u].size()) {
  158.             relabel(u);
  159.             p[u] = 0;
  160.         }
  161.         int i = g[u][p[u]];
  162.         if (e[i].f < e[i].c && e[i].cost + price[u] - price[e[i].v] < -epsilon) {
  163.             push(i);
  164.         }
  165.         ++p[u];
  166.         if (excess[u] == 0) {
  167.             break;
  168.         }
  169.     }
  170. }
  171.  
  172. void refine() {
  173.     used.assign(n, false);
  174.     p.assign(n, 0);
  175.     for (int i = 0; i < e.size(); ++i) {
  176.         int u = e[i].u;
  177.         int v = e[i].v;
  178.         if (e[i].f < e[i].c && e[i].cost + price[u] - price[v] < epsilon) {
  179.             int delta = e[i].c - e[i].f;
  180.             e[i].f += delta;
  181.             e[i ^ 1].f -= delta;
  182.             excess[u] -= delta;
  183.             excess[v] += delta;
  184.         }
  185.     }
  186.     for (int i = 0; i < n; ++i) {
  187.         if (excess[i] > 0) {
  188.             q.push_back(i);
  189.         } else if (excess[i] < 0) {
  190.             neg.insert(i);
  191.         }
  192.     }
  193.     // print_edges();
  194.     while (q.size() > 0) {
  195.         int v = q.front();
  196.         used[v] = false;
  197.         q.pop_front();
  198.         discharge(v);
  199.         // ++relabels;
  200.         if (relabels == n / 4) {
  201.             // price_update();
  202.             relabels = 0;
  203.         }
  204.     }
  205. }
  206.  
  207. ll min_cost() {
  208.     neg.reserve(1024);
  209.     neg.max_load_factor(0.25);
  210.     vis.reserve(1024);
  211.     vis.max_load_factor(0.25);
  212.     prices_used.assign(n, false);
  213.     excess.assign(n, 0);
  214.     price.assign(n, 0);
  215.     while (eps > 0.99 / n) {
  216.         eps /= 2;
  217.         refine();
  218.     }
  219.     ll ans = 0;
  220.     for (int i = 0; i < e.size(); ++i) {
  221.         ans += e[i].cost * e[i].f;
  222.     }
  223.     return ans / 2;
  224. }
  225.  
  226. void add_edge(int from, int to, int cap, int cost, int num) {
  227.     e.push_back(edge(from, to, cap, cost, num));
  228.     e.push_back(edge(to, from, 0, -cost, num));
  229.     g[from].push_back(e.size() - 2);
  230.     g[to].push_back(e.size() - 1);
  231. }
  232. vector<vector<int>> dc;
  233. vector<int> path;
  234.  
  235. int dfs1(int v, int minc) {
  236.     if (used[v]) return false;
  237.     used[v] = true;
  238.     if (v == t) {
  239.         dc.push_back(path);
  240.         return minc;
  241.     }
  242.     for (int i : g[v]) {
  243.         if (e[i].f <= 0) continue;
  244.         path.push_back(e[i].num);
  245.         int d = dfs1(e[i].v, min(e[i].f, minc));
  246.         if (d) {
  247.             e[i].f -= d;
  248.             e[i ^ 1].f += d;
  249.             return true;
  250.         }
  251.         path.pop_back();
  252.     }
  253.     return false;
  254. }
  255.  
  256.  
  257. int main(int argc, char** argv) {
  258.     ios_base::sync_with_stdio(false);
  259.     cin.tie(0);
  260.     int z, w;
  261.     cin >> z >> w;
  262.     n = z + 2;
  263.     s = 0;
  264.     t = z + 1;
  265.     g.assign(n, vector<int>());
  266.     p.assign(n, 0);
  267.     for (int i = 1; i <= z / 2; ++i) {
  268.         add_edge(s, i, 1, 0, i);
  269.     }
  270.     for (int i = z / 2 + 1; i <= z; ++i) {
  271.         add_edge(i, t, 1, 0, i);
  272.     }
  273.     int u, v, c;
  274.     for (int i = 0; i < w; ++i) {
  275.         cin >> u >> v >> c;
  276.         add_edge(u, v, 1, c, v);
  277.     }
  278.     dinic(1, inf);
  279.     before = clock();
  280.     ll cost = min_cost();
  281.     after = clock();
  282.     cout << cost << '\n';
  283.     /*do {
  284.         path.clear();
  285.         used.assign(n, false);
  286.     } while (dfs1(s, inf));
  287.     for (auto path : dc) {
  288.         cout << path[0] << ' ' << path[1] << '\n';
  289.     }*/
  290.     cout << fixed << setprecision(6) << (after - before) / CLOCKS_PER_SEC << '\n';
  291. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement