| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094583 | TIN | Domino (COCI15_domino) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define FNAME "test"
typedef long long ll;
const ll oo = 1e18 + 1;
struct Edge {
int from, to, cap;
ll cost;
Edge(int from, int to, int cap, ll cost) : from(from), to(to), cap(cap), cost(cost) {}
};
struct MinFlow {
int n, k, s, t;
vector<vector<int>> adj;
vector<vector<ll>> cap;
vector<vector<ll>> cost;
MinFlow(int _n, int _k, int _s, int _t) {
n = _n;
k = _k;
s = _s;
t = _t;
adj.assign(n, vector<int>());
cost.assign(n, vector<ll>(n, 0));
cap.assign(n, vector<ll>(n, 0));
}
void addEdge(Edge e) {
adj[e.from].push_back(e.to);
adj[e.to].push_back(e.from);
cost[e.from][e.to] = e.cost;
cost[e.to][e.from] = -e.cost;
cap[e.from][e.to] = e.cap;
}
void shortest_paths(int v0, vector<ll>& d, vector<int>& p) {
d.assign(n, oo);
d[v0] = 0;
vector<bool> inq(n, false);
queue<int> q;
q.push(v0);
p.assign(n, -1);
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (int v : adj[u]) {
if (cap[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
d[v] = d[u] + cost[u][v];
p[v] = u;
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
}
ll min_cost_flow() {
int flow = 0;
ll cost = 0;
vector<ll> d;
vector<int> p;
while (flow < k) {
shortest_paths(s, d, p);
if (d[t] == oo) break;
int f = k - flow;
int cur = t;
while (cur != s) {
f = min(f, cap[p[cur]][cur]);
cur = p[cur];
}
flow += f;
cost += 1LL * f * d[t];
cur = t;
while (cur != s) {
cap[p[cur]][cur] -= f;
cap[cur][p[cur]] += f;
cur = p[cur];
}
}
if (flow < k) return -1;
return cost;
}
};
int n, k;
ll sum, ans;
void Task() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(9);
if (fopen(FNAME".inp","r")) {
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
void Solve() {
//Your Code
cin >> n >> k;
MinFlow calc(n * n + 5, k, 0, n * n + 1);
sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ll x;
cin >> x;
sum += x;
int id = (i - 1) * n + j;
if ((i + 1 + j) & 1) {
calc.addEdge(Edge(0, id, 1, -x));
if (i > 1) calc.addEdge(Edge(id, id - n, 1, 0));
if (j > 1) calc.addEdge(Edge(id, id - 1, 1, 0));
} else {
calc.addEdge(Edge(id, n * n + 1, 1, -x));
if (i > 1) calc.addEdge(Edge(id - n, id, 1, 0));
if (j > 1) calc.addEdge(Edge(id - 1, id, 1, 0));
}
}
}
ans = calc.min_cost_flow();
cout << sum + ans << '\n';
}
int main() {
Task();
Solve();
cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
return 37^37;
}