Difference between revisions of "CodeArchive MinCostMaxFlow"
From Ubcacm
Line 1: | Line 1: | ||
+ | This works, there should be no negative edges in the beginning (I'll need to re-weight otherwise) | ||
+ | <pre> | ||
+ | // assumes that the opposite edge has opposite cost make sure to understand that!!! | ||
+ | // watch for potential function overflow | ||
+ | const int N = 128; | ||
+ | const ll infll = 1ll << 50; | ||
+ | const int infint = 1 << 30; | ||
+ | int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], vis[N], s; | ||
+ | ll pot[N], dist[N]; | ||
+ | |||
+ | void add_edge(int a, int b, int c, int p){ | ||
+ | adj[a][sz[a]] = b, cost[a][sz[a]] = p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b]; | ||
+ | adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a]; | ||
+ | sz[a]++, sz[b]++; | ||
+ | } | ||
+ | |||
+ | int mcf_update(int s, int t, ll &price, int n){ | ||
+ | for(int i = 0; i < n; i++) par[i] = -1, vis[i] = 0, dist[i] = infll; // init | ||
+ | dist[s] = 0; | ||
+ | // do dijkstra | ||
+ | while(true){ | ||
+ | ll best = infll; int id = -1; | ||
+ | for(int i = 0; i < n; i++) if(!vis[i] && dist[i] < best) best = dist[i], id = i; | ||
+ | if(id == -1) break; vis[id] = 1; | ||
+ | for(int i = 0; i < sz[id]; i++) | ||
+ | if(flo[id][i] < cap[id][i] && dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]] < dist[adj[id][i]]) | ||
+ | dist[adj[id][i]] = dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]], par[adj[id][i]] = other[id][i]; | ||
+ | } | ||
+ | if(dist[t] >= infll) return 0; int mx = infint; | ||
+ | for(int i = t; i != s; i = adj[i][par[i]]){ | ||
+ | int prev = adj[i][par[i]], id = other[i][par[i]]; | ||
+ | mx <?= (cap[prev][id] - flo[prev][id]); | ||
+ | } | ||
+ | for(int i = t; i != s; i = adj[i][par[i]]){ | ||
+ | int prev = adj[i][par[i]], id = other[i][par[i]]; | ||
+ | flo[prev][id] += mx; flo[i][par[i]] -= mx; | ||
+ | price += cost[prev][id]*(ll)mx; | ||
+ | } | ||
+ | for(int i = 0; i < n; i++) if(pot[i] < infll) pot[i] += dist[i]; | ||
+ | return mx; | ||
+ | } | ||
+ | |||
+ | // usage: | ||
+ | //ll price = 0; | ||
+ | //memset(pot, 0, sizeof(pot)); | ||
+ | //while(mcf_update(source, sink, price, sink + 1)); | ||
+ | </pre> | ||
+ | |||
+ | |||
+ | This works, definitely, even with negative edges: | ||
+ | <pre> | ||
+ | // assumes that the opposite edge has opposite cost make sure to understand that!!! | ||
+ | const int N = 128; | ||
+ | const int inf = 1000000000; | ||
+ | int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], dist[N], s; | ||
+ | |||
+ | void add_edge(int a, int b, int c, int p){ | ||
+ | adj[a][sz[a]] = b, cost[a][sz[a]] = p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b]; | ||
+ | adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a]; | ||
+ | sz[a]++, sz[b]++; | ||
+ | } | ||
+ | |||
+ | int mcf_update(int s, int t, int &price, int n){ | ||
+ | for(int i = 0; i < n; i++) par[i] = -1, dist[i] = inf; // init | ||
+ | dist[s] = 0; | ||
+ | // do bellman-ford | ||
+ | for(int k = 0; k < n; k++) | ||
+ | for(int i = 0; i < n; i++) | ||
+ | for(int j = 0; j < sz[i]; j++) | ||
+ | if(flo[i][j] < cap[i][j] && dist[i] + cost[i][j] < dist[adj[i][j]]) | ||
+ | dist[adj[i][j]] = dist[i] + cost[i][j], par[adj[i][j]] = other[i][j]; | ||
+ | |||
+ | if(dist[t] >= inf) return 0; int mx = inf; | ||
+ | for(int i = t; i != s; i = adj[i][par[i]]){ | ||
+ | int prev = adj[i][par[i]], id = other[i][par[i]]; | ||
+ | mx <?= (cap[prev][id] - flo[prev][id]); | ||
+ | } | ||
+ | for(int i = t; i != s; i = adj[i][par[i]]){ | ||
+ | int prev = adj[i][par[i]], id = other[i][par[i]]; | ||
+ | flo[prev][id] += mx; flo[i][par[i]] -= mx; | ||
+ | price += cost[prev][id]*mx; | ||
+ | } | ||
+ | |||
+ | return mx; | ||
+ | } | ||
+ | |||
+ | // usage: | ||
+ | //int price = 0; | ||
+ | //while(mcf_update(source, sink, price, sink + 1)); | ||
+ | </pre> | ||
+ | |||
+ | |||
As used to get the 1st place on 10594. | As used to get the 1st place on 10594. | ||
Latest revision as of 22:10, 6 February 2007
This works, there should be no negative edges in the beginning (I'll need to re-weight otherwise)
// assumes that the opposite edge has opposite cost make sure to understand that!!! // watch for potential function overflow const int N = 128; const ll infll = 1ll << 50; const int infint = 1 << 30; int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], vis[N], s; ll pot[N], dist[N]; void add_edge(int a, int b, int c, int p){ adj[a][sz[a]] = b, cost[a][sz[a]] = p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b]; adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a]; sz[a]++, sz[b]++; } int mcf_update(int s, int t, ll &price, int n){ for(int i = 0; i < n; i++) par[i] = -1, vis[i] = 0, dist[i] = infll; // init dist[s] = 0; // do dijkstra while(true){ ll best = infll; int id = -1; for(int i = 0; i < n; i++) if(!vis[i] && dist[i] < best) best = dist[i], id = i; if(id == -1) break; vis[id] = 1; for(int i = 0; i < sz[id]; i++) if(flo[id][i] < cap[id][i] && dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]] < dist[adj[id][i]]) dist[adj[id][i]] = dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]], par[adj[id][i]] = other[id][i]; } if(dist[t] >= infll) return 0; int mx = infint; for(int i = t; i != s; i = adj[i][par[i]]){ int prev = adj[i][par[i]], id = other[i][par[i]]; mx <?= (cap[prev][id] - flo[prev][id]); } for(int i = t; i != s; i = adj[i][par[i]]){ int prev = adj[i][par[i]], id = other[i][par[i]]; flo[prev][id] += mx; flo[i][par[i]] -= mx; price += cost[prev][id]*(ll)mx; } for(int i = 0; i < n; i++) if(pot[i] < infll) pot[i] += dist[i]; return mx; } // usage: //ll price = 0; //memset(pot, 0, sizeof(pot)); //while(mcf_update(source, sink, price, sink + 1));
This works, definitely, even with negative edges:
// assumes that the opposite edge has opposite cost make sure to understand that!!! const int N = 128; const int inf = 1000000000; int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], dist[N], s; void add_edge(int a, int b, int c, int p){ adj[a][sz[a]] = b, cost[a][sz[a]] = p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b]; adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a]; sz[a]++, sz[b]++; } int mcf_update(int s, int t, int &price, int n){ for(int i = 0; i < n; i++) par[i] = -1, dist[i] = inf; // init dist[s] = 0; // do bellman-ford for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < sz[i]; j++) if(flo[i][j] < cap[i][j] && dist[i] + cost[i][j] < dist[adj[i][j]]) dist[adj[i][j]] = dist[i] + cost[i][j], par[adj[i][j]] = other[i][j]; if(dist[t] >= inf) return 0; int mx = inf; for(int i = t; i != s; i = adj[i][par[i]]){ int prev = adj[i][par[i]], id = other[i][par[i]]; mx <?= (cap[prev][id] - flo[prev][id]); } for(int i = t; i != s; i = adj[i][par[i]]){ int prev = adj[i][par[i]], id = other[i][par[i]]; flo[prev][id] += mx; flo[i][par[i]] -= mx; price += cost[prev][id]*mx; } return mx; } // usage: //int price = 0; //while(mcf_update(source, sink, price, sink + 1));
As used to get the 1st place on 10594.
int cap[N][N], flo[N][N], cost[N][N], vis[N], pot[N], par[N], dist[N], inf = 1000000000; int mcf_update(int s, int t, ll &price){ for(int i = 0; i < n; i++) dist[i] = inf, vis[i] = 0; dist[s] = 0; while(true){ int best = inf, ind = -1; for(int i = 0; i < n; i++) if(!vis[i] && dist[i] < best) best = dist[ind = i]; if(ind == -1) break; vis[ind] = 1; for(int i = 0; i < n; i++) if(!vis[i] && flo[ind][i] < cap[ind][i]){ int pr = (flo[ind][i] >= 0 ? cost[ind][i] : -cost[ind][i]) + pot[ind] - pot[i]; if(pr + dist[ind] < dist[i]) dist[i] = pr + dist[par[i] = ind]; } } if(!vis[t]) return 0; for(int i = 0; i < n; i++) if(pot[i] < inf) pot[i] += dist[i]; int mx = inf; for(int j = t, i = par[t]; j != s; j = i, i = par[i]) mx <?= (flo[i][j] >= 0 ? (cap[i][j] - flo[i][j]) : -flo[i][j]); for(int j = t, i = par[t]; j != s; j = i, i = par[i]) if(flo[i][j] >= 0) flo[i][j] += mx, flo[j][i] -= mx, price += (ll)cost[i][j]*mx; else flo[i][j] += mx, flo[j][i] -= mx, price -= (ll)cost[i][j]*mx; return mx; } // usage // int price = 0, change = 0; // memset(pot, 0, sizeof(pot)); // do{ d -= change; } while(d && (change = mcf_update(0, n - 1, price)));
-- Main.YuryKholondyrev - 03 Mar 2006