| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 875859 | serifefedartar | 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 fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 5e6 + 101;
struct Edge {
int from, to, cost;
char cap;
Edge() { }
Edge(int _from, int _to, int _cost, char _cap) : from(_from), to(_to), cost(_cost), cap(_cap) { }
};
struct Flow {
vector<Edge> edges;
vector<vector<int>> graph;
vector<short> dist, from;
int Q, source, terminal;
Flow(int n) {
Q = -1;
graph = vector<vector<int>>(n + 10);
dist = vector<int>(n + 10);
from = vector<int>(n + 10);
}
void addEdge(int from, int to, int cost, int cap) {
Q++;
edges.push_back(Edge(from, to, cost, cap));
graph[from].push_back(Q);
Q++;
edges.push_back(Edge(to, from, -cost, 0));
graph[to].push_back(Q);
}
bool shortestPath() {
for (int i = 0; i < dist.size(); i++)
dist[i] = 10000;
dist[source] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, source});
while (!pq.empty()) {
int node = pq.top().s;
int d = pq.top().f;
pq.pop();
for (auto u : graph[node]) {
if (edges[u].cap && dist[edges[u].to] > edges[u].cost + d) {
dist[edges[u].to] = edges[u].cost + d;
from[edges[u].to] = u;
pq.push({dist[edges[u].to], edges[u].to});
}
}
}
return (dist[terminal] != 1e8);
}
ll minCost() {
ll cost = 0;
while (shortestPath()) {
cost += dist[terminal];
int now = terminal;
while (now != source) {
int edge_id = from[now];
int from = edges[edge_id].from;
now = from;
edges[edge_id].cap--;
edges[edge_id ^ 1].cap++;
}
}
return cost;
}
};
int grid[2005][2005];
int main() {
fast
int N, K;
cin >> N >> K;
ll ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
cin >> grid[i][j];
ans += grid[i][j];
}
}
Flow F = Flow(N * N + 10);
F.addEdge(N * N + 2, 0, 0, K);
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
if ((i + 1 + j) % 2)
F.addEdge(0, i * N + j, -grid[i][j], 1);
}
}
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
if ((i + 1 + j) % 2) {
if (j != N)
F.addEdge(i * N + j, i * N + j + 1, 0, 1);
if (i != N - 1)
F.addEdge(i * N + j, (i+1) * N + j, 0, 1);
if (j != 1)
F.addEdge(i * N + j, i * N + j - 1, 0, 1);
if (i != 0)
F.addEdge(i * N + j, (i-1) * N + j, 0, 1);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
if ((i + 1 + j) % 2 == 0)
F.addEdge(i * N + j, N * N + 1, -grid[i][j], 1);
}
}
F.source = N * N + 2, F.terminal = N * N + 1;
ans += F.minCost();
cout << ans << "\n";
}