이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct mincost {
const long INF = 1e18;
struct edge {
int src, dst, maxCap, cost, flw, cap;
};
vector<edge> edges;
vector<vector<int>> graph;
vector<long> phi;
void dijkstra(int s, vector<long> &d, vector<int> &prev) {
std::fill(d.begin(), d.end(), INF);
d[s] = 0;
std::priority_queue<pair<long, int>> pq;
pq.push({-d[s], s});
while (!pq.empty()) {
int v = pq.top().second;
long cur_d = -pq.top().first;
pq.pop();
if (cur_d > d[v]) continue;
for (int j = 0; j < graph[v].size(); ++j) {
edge &e = edges[graph[v][j]];
if (e.flw == e.cap) continue;
long dd = d[v] + e.cost + phi[e.src] - phi[e.dst];
if (dd < d[e.dst]) {
d[e.dst] = dd;
prev[e.dst] = graph[v][j];
pq.push({-d[e.dst], e.dst});
}
}
}
}
void init(int n) {
graph.resize(n);
phi.resize(n);
}
void validate() {
for (edge &e: edges) {
if (e.flw < e.cap) {
int x = e.src;
int y = e.dst;
assert (e.cost + phi[x] - phi[y] >= 0);
}
}
}
long cost = 0;
void doubleFlow() {
for (auto &e: edges) {
e.cap *= 2;
e.flw *= 2;
}
cost *= 2;
}
void incCapacity(int i) {
auto &e = edges[i];
auto &er = edges[i ^ 1];
{
if (e.cost + phi[e.src] - phi[e.dst] >= 0) {
e.cap++;
return;
}
}
int n = graph.size();
vector<long> dist(n);
vector<int> prev(n);
int s = e.dst;
int t = e.src;
dijkstra(s, dist, prev);
long d2 = dist[t] - phi[s] + phi[t];
if (d2 + e.cost < 0) {
i = t;
while (i != s) {
edge &e = edges[prev[i]];
edge &er = edges[prev[i] ^ 1];
e.flw++;
er.flw--;
cost += (long) e.cost;
i = e.src;
}
e.flw++;
er.flw--;
}
e.cap++;
for (int i = 0; i < n; i++) {
if (dist[i] != INF) phi[i] += dist[i];
}
long dd = 0;
for (auto &e: edges) {
if (e.flw == e.cap) continue;
long c = e.cost + phi[e.src] - phi[e.dst];
dd = max(dd, -c);
}
for (int i = 0; i < n; i++) {
if (dist[i] == INF) phi[i] += dd;
}
validate();
}
void minCostCirculation() {
int n = graph.size();
int m = edges.size() / 2;
validate();
for (int i = 30; i >= 0; i--) {
doubleFlow();
for (int j = 0; j < m; j++) {
if (edges[2 * j].maxCap & (1 << i)) {
incCapacity(2 * j);
}
}
}
}
void fordBellman() {
int n = graph.size();
for (int i = 0; i < n; i++) {
phi[i] = INF;
}
bool ok = false;
int c = 0;
while (!ok) {
c++;
assert(c <= n);
ok = true;
for (edge &e: edges) {
if (e.flw < e.cap) {
int x = e.src;
int y = e.dst;
if (phi[y] > phi[x] + e.cost) {
phi[y] = phi[x] + e.cost;
ok = false;
}
}
}
}
}
int minCostFlow(int s, int t) {
int n = graph.size();
int m = edges.size();
for (auto &e: edges) e.cap = e.maxCap;
fordBellman();
vector<long> dist(n);
vector<int> prev(n);
int fl = 0;
while (true) {
dijkstra(s, dist, prev);
if (dist[t] == INF) break;
// if (dist[t] - phi[s] + phi[t] >= 0) break;
{
int i = t;
int delta = INT_MAX;
while (i != s) {
edge &e = edges[prev[i]];
delta = std::min(delta, e.cap - e.flw);
i = e.src;
}
assert(delta >= 0);
fl += delta;
i = t;
while (i != s) {
edge &e = edges[prev[i]];
edge &er = edges[prev[i] ^ 1];
e.flw += delta;
er.flw -= delta;
assert(e.flw <= e.cap);
cost += (long) e.cost * delta;
i = e.src;
}
}
for (int i = 0; i < n; i++) {
phi[i] += dist[i];
}
}
return fl;
}
void addEdge(int u, int v, int cap, int cost) {
edges.push_back({u, v, cap, cost, 0, 0});
edges.push_back({v, u, 0, -cost, 0, 0});
graph[u].push_back(edges.size() - 2);
graph[v].push_back(edges.size() - 1);
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a[i] = x - y;
}
mincost mc;
mc.init(n + 2);
int s = n;
int t = n + 1;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
mc.addEdge(s, i, -a[i], 0);
} else {
mc.addEdge(i, t, a[i], 0);
}
if (i < n - 1) {
mc.addEdge(i, i + 1, INT_MAX, 1);
mc.addEdge(i + 1, i, INT_MAX, 1);
}
}
mc.minCostFlow(s, t);
cout << mc.cost << "\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bulves.cpp: In member function 'void mincost::dijkstra(int, std::vector<long long int>&, std::vector<int>&)':
bulves.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int j = 0; j < graph[v].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~
bulves.cpp: In member function 'void mincost::minCostCirculation()':
bulves.cpp:116:13: warning: unused variable 'n' [-Wunused-variable]
116 | int n = graph.size();
| ^
bulves.cpp: In member function 'int mincost::minCostFlow(int, int)':
bulves.cpp:155:13: warning: unused variable 'm' [-Wunused-variable]
155 | int m = edges.size();
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |