Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- struct edge {
- int u, v, c, f, cost, num;
- edge(int from, int to, int cap, int cost, int num):u(from), v(to), c(cap), f(0), cost(cost), num(num){}
- };
- int inf = 2e9;
- vector<edge> e;
- vector<vector<int>> g;
- vector<int> p;
- vector<int> dist;
- vector<char> used;
- int n, m, s, t;
- double before, after;
- void print_edges() {
- for (int i = 0; i < e.size(); i += 2) {
- cout << e[i].u << ' ' << e[i].v << ' ' << e[i].f << ' ' << e[i].c << ' ' << e[i].cost << endl;
- }
- cout << "-------" << endl;
- }
- int bfs(int maxc) {
- dist.assign(n, inf);
- queue<int> q;
- q.push(s);
- dist[s] = 0;
- while (q.size() > 0) {
- int v = q.front();
- q.pop();
- for (int i : g[v]) {
- int to = e[i].v;
- if (e[i].c - e[i].f < maxc) continue;
- if (dist[to] == inf) {
- dist[to] = dist[v] + 1;
- q.push(to);
- }
- }
- }
- return dist[t];
- }
- int dfs(int v, int minc, int maxc) {
- if (used[v]) return 0;
- used[v] = true;
- if (v == t || minc == 0) {
- return minc;
- }
- for (; p[v] < g[v].size(); p[v]++) {
- int i = g[v][p[v]];
- if (e[i].c - e[i].f < maxc || dist[e[i].v] != dist[v] + 1) continue;
- int delta = dfs(e[i].v, min(minc, e[i].c - e[i].f), maxc);
- if (delta > 0) {
- e[i].f += delta;
- e[i ^ 1].f -= delta;
- return delta;
- }
- }
- return 0;
- }
- int dinic(int maxc, int need) {
- int flow = 0;
- while (bfs(maxc) != inf) {
- p.assign(n, 0);
- int added = 0;
- do {
- used.assign(n, false);
- added = dfs(s, need, maxc);
- flow += added;
- need -= added;
- } while (added > 0);
- if (need == 0) {
- break;
- }
- }
- return flow;
- }
- vector<double> price;
- vector<int> excess;
- deque<int> q;
- double eps = 1e6;
- double epsilon = 1e-8;
- int relabels = 0;
- vector<char> prices_used;
- unordered_set<int> neg;
- unordered_set<int> vis;
- void dfs_update(int u) {
- prices_used[u] = true;
- vis.insert(u);
- for (int i : g[u]) {
- int v = e[i].v;
- if (e[i ^ 1].f == e[i ^ 1].c || e[i ^ 1].cost + price[v] - price[u] > 0) continue;
- if (!prices_used[v]) {
- dfs_update(v);
- }
- }
- }
- void price_update() {
- vis.clear();
- for (int v : neg) {
- if (!prices_used[v]) {
- dfs_update(v);
- }
- }
- for (int v : q) {
- if (!prices_used[v] && !vis.count(v)) {
- price[v] -= eps;
- }
- }
- for (int v : vis) {
- prices_used[v] = false;
- }
- }
- void push(int i) {
- int u = e[i].u;
- int v = e[i].v;
- int delta = min(e[i].c - e[i].f, excess[u]);
- e[i].f += delta;
- e[i ^ 1].f -= delta;
- excess[u] -= delta;
- excess[v] += delta;
- if (excess[v] - delta < 0 && excess[v] >= 0) {
- neg.erase(i);
- }
- if (excess[v] > 0 && !used[v]) {
- used[v] = true;
- q.push_back(v);
- }
- }
- void relabel(int u) {
- ++relabels;
- double next = -1e18;
- for (int i : g[u]) {
- int v = e[i].v;
- if (e[i].f < e[i].c) {
- next = max(next, price[v] - e[i].cost - eps);
- }
- }
- price[u] = next;
- // price[u] -= eps;
- }
- void discharge(int u) {
- while (true) {
- if (p[u] == g[u].size()) {
- relabel(u);
- p[u] = 0;
- }
- int i = g[u][p[u]];
- if (e[i].f < e[i].c && e[i].cost + price[u] - price[e[i].v] < -epsilon) {
- push(i);
- }
- ++p[u];
- if (excess[u] == 0) {
- break;
- }
- }
- }
- void refine() {
- used.assign(n, false);
- p.assign(n, 0);
- for (int i = 0; i < e.size(); ++i) {
- int u = e[i].u;
- int v = e[i].v;
- if (e[i].f < e[i].c && e[i].cost + price[u] - price[v] < epsilon) {
- int delta = e[i].c - e[i].f;
- e[i].f += delta;
- e[i ^ 1].f -= delta;
- excess[u] -= delta;
- excess[v] += delta;
- }
- }
- for (int i = 0; i < n; ++i) {
- if (excess[i] > 0) {
- q.push_back(i);
- } else if (excess[i] < 0) {
- neg.insert(i);
- }
- }
- // print_edges();
- while (q.size() > 0) {
- int v = q.front();
- used[v] = false;
- q.pop_front();
- discharge(v);
- // ++relabels;
- if (relabels == n / 4) {
- // price_update();
- relabels = 0;
- }
- }
- }
- ll min_cost() {
- neg.reserve(1024);
- neg.max_load_factor(0.25);
- vis.reserve(1024);
- vis.max_load_factor(0.25);
- prices_used.assign(n, false);
- excess.assign(n, 0);
- price.assign(n, 0);
- while (eps > 0.99 / n) {
- eps /= 2;
- refine();
- }
- ll ans = 0;
- for (int i = 0; i < e.size(); ++i) {
- ans += e[i].cost * e[i].f;
- }
- return ans / 2;
- }
- void add_edge(int from, int to, int cap, int cost, int num) {
- e.push_back(edge(from, to, cap, cost, num));
- e.push_back(edge(to, from, 0, -cost, num));
- g[from].push_back(e.size() - 2);
- g[to].push_back(e.size() - 1);
- }
- vector<vector<int>> dc;
- vector<int> path;
- int dfs1(int v, int minc) {
- if (used[v]) return false;
- used[v] = true;
- if (v == t) {
- dc.push_back(path);
- return minc;
- }
- for (int i : g[v]) {
- if (e[i].f <= 0) continue;
- path.push_back(e[i].num);
- int d = dfs1(e[i].v, min(e[i].f, minc));
- if (d) {
- e[i].f -= d;
- e[i ^ 1].f += d;
- return true;
- }
- path.pop_back();
- }
- return false;
- }
- int main(int argc, char** argv) {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int z, w;
- cin >> z >> w;
- n = z + 2;
- s = 0;
- t = z + 1;
- g.assign(n, vector<int>());
- p.assign(n, 0);
- for (int i = 1; i <= z / 2; ++i) {
- add_edge(s, i, 1, 0, i);
- }
- for (int i = z / 2 + 1; i <= z; ++i) {
- add_edge(i, t, 1, 0, i);
- }
- int u, v, c;
- for (int i = 0; i < w; ++i) {
- cin >> u >> v >> c;
- add_edge(u, v, 1, c, v);
- }
- dinic(1, inf);
- before = clock();
- ll cost = min_cost();
- after = clock();
- cout << cost << '\n';
- /*do {
- path.clear();
- used.assign(n, false);
- } while (dfs1(s, inf));
- for (auto path : dc) {
- cout << path[0] << ' ' << path[1] << '\n';
- }*/
- cout << fixed << setprecision(6) << (after - before) / CLOCKS_PER_SEC << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement