Загрузка данных
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const ll inf = 1LL << 61;
struct MCMF {
struct Edge {
int from, to;
ll cap, cost;
Edge(int _from, int _to, ll _cap, ll _cost) {
from = _from;
to = _to;
cap = _cap;
cost = _cost;
}
};
int n, s, t;
ll flow, min_cost;
vector<vector<int>> g;
vector<Edge> e;
vector<ll> d, potential;
vector<int> par;
bool neg;
MCMF() {}
MCMF(int _n) { // 0-based indexing
n = _n + 10;
g.assign(n, vector<int>());
neg = false;
}
void add_edge(int u, int v, ll cap, ll cost, bool directed = true) {
if (cost < 0)
neg = true;
g[u].emplace_back((int) e.size());
e.emplace_back(u, v, cap, cost);
g[v].emplace_back((int) e.size());
e.emplace_back(v, u, 0, -cost);
if (!directed)
add_edge(v, u, cap, cost, true);
}
bool dijkstra() {
par.assign(n, -1);
d.assign(n, inf);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
d[s] = 0;
q.emplace(0, s);
while (!q.empty()) {
int from = q.top().second;
ll nw = q.top().first;
q.pop();
if (nw != d[from])
continue;
for (int id : g[from]) {
int to = e[id].to;
ll cap = e[id].cap;
ll w = e[id].cost + potential[from] - potential[to];
if (d[from] + w < d[to] && cap > 0) {
d[to] = d[from] + w;
par[to] = id;
q.emplace(d[to], to);
}
}
}
for (int i = 0; i < n; i++) {
if (d[i] < inf)
d[i] += (potential[i] - potential[s]);
}
for (int i = 0; i < n; i++) {
if (d[i] < inf)
potential[i] = d[i];
}
return d[t] != inf;
}
ll send_flow(int v, ll cur) {
if (par[v] == -1)
return cur;
int id = par[v];
int from = e[id].from;
ll w = e[id].cost;
ll f = send_flow(from, min(cur, e[id].cap));
min_cost += f * w;
e[id].cap -= f;
e[id ^ 1].cap += f;
return f;
}
// returns {maxflow, mincost}
pair<ll, ll> solve(int _s, int _t, ll goal = inf) {
s = _s;
t = _t;
flow = 0, min_cost = 0;
potential.assign(n, 0);
if (neg) {
d.assign(n, inf);
d[s] = 0;
bool relax = true;
for (int i = 0; i < n && relax; i++) {
relax = false;
for (int from = 0; from < n; from++) {
for (int id : g[from]) {
int v = e[id].to;
ll cap = e[id].cap, w = e[id].cost;
if (d[v] > d[from] + w && cap > 0) {
d[v] = d[from] + w;
relax = true;
}
}
}
}
for (int i = 0; i < n; i++)
if (d[i] < inf)
potential[i] = d[i];
}
while (flow < goal && dijkstra())
flow += send_flow(t, goal - flow);
return {flow, min_cost};
}
};
void solve() {
int st = 0, fin = 11;
MCMF mcmf(12);
mcmf.add_edge(st, 1, 150, 0);
mcmf.add_edge(st, 2, 120, 0);
mcmf.add_edge(st, 3, 180, 0);
mcmf.add_edge(st, 4, 150, 0);
vector<vector<int>> costs = {
{5, 8, 2, 6, 9, 4},
{7, 4, 8, 1, 5, 3},
{6, 2, 5, 9, 3, 7},
{8, 9, 3, 4, 6, 2}
};
vector<int> bi = {5, 6, 7, 8, 9, 10};
for (int i = 1; i <= 4; i++) {
for (int j = 0; j < bi.size(); j++) {
mcmf.add_edge(i, bi[j], inf, costs[i - 1][j]);
}
}
mcmf.add_edge(5, fin, 90, 0);
mcmf.add_edge(6, fin, 80, 0);
mcmf.add_edge(7, fin, 110, 0);
mcmf.add_edge(8, fin, 100, 0);
mcmf.add_edge(9, fin, 120, 0);
mcmf.add_edge(10, fin, 100, 0);
auto [flow, cost] = mcmf.solve(st, fin);
cout << flow << " " << cost << endl; // 600 1580
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}