QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #528057 | #6113. Window Arrangement | fishy15 | WA | 56ms | 3964kb | C++20 | 9.4kb | 2024-08-23 06:09:17 | 2024-08-23 06:09:18 |
Judging History
answer
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <numeric>
#include <cassert>
#define ll long long
#define ld long double
#define MOD 1000000007
#define INFLL 0x3f3f3f3f3f3f3f3f
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
using vi = vector<int>;
template<class T, class C>
struct flow_network_weighted{
struct E{
int from, to;
T capacity, flow;
C cost;
bool saturated() const{
static constexpr T eps = 1e-9;
return capacity - flow <= eps;
}
};
int n;
vector<vector<int>> adj;
vector<E> edge;
C cost = 0;
flow_network_weighted(int n): n(n), adj(n){ }
void clear_flow(){
for(auto &e: edge) e.flow = 0;
cost = 0;
}
int link(int from, int to, T cap, C cost){
assert(0 <= min(from, to) && max(from, to) < n && cap >= 0 && cost >= 0);
int ind = orient(from, to, cap, cost);
orient(to, from, cap, cost);
return ind;
}
int orient(int from, int to, T cap, C cost){
assert(0 <= min(from, to) && max(from, to) < n && cap >= 0);
int ind = (int)edge.size();
adj[from].push_back((int)edge.size());
edge.push_back({from, to, cap, 0, cost});
adj[to].push_back((int)edge.size());
edge.push_back({to, from, 0, 0, -cost});
return ind;
}
void add_flow(int i, T f){
edge[i].flow += f;
cost += f * edge[i].cost;
edge[i ^ 1].flow -= f;
}
friend ostream &operator<<(ostream &out, const flow_network_weighted &F){
out << "\n";
for(auto i = 0; i < (int)F.edge.size(); i += 2){
auto &e = F.edge[i];
out << "{" << e.from << " -> " << e.to << ", " << e.cost << ", " << e.flow << "/" << e.capacity << "}\n";
}
return out;
}
};
template<class T, class C>
struct minimum_cost_maximum_flow_johnson{
#ifdef LOCAL
#define ASSERT(x) assert(x)
#else
#define ASSERT(x) 42
#endif
static constexpr T eps = (T) 1e-9;
flow_network_weighted<T, C> &F;
minimum_cost_maximum_flow_johnson(flow_network_weighted<T, C> &F): F(F), h(F.n), h_next(F.n){}
vector<C> h, h_next;
vector<int> in_queue, q, pe, stack, state, done;
priority_queue<pair<C, int>, vector<pair<C, int>>, greater<>> pq;
bool _try_cycle_cancelling(){
fill(h.begin(), h.end(), 0);
q.resize(F.n);
iota(q.begin(), q.end(), 0);
in_queue.assign(F.n, false);
pe.assign(F.n, -1);
auto detect_cycle = [&]()->bool{
stack.clear();
fill(state.begin(), state.end(), 0);
for(auto s = 0; s < F.n; ++ s){
if(state[s]) continue;
for(auto u = s; ; ){
if(state[u]){
if(state[u] == 1){
stack.erase(stack.begin(), find(stack.begin(), stack.end(), u));
assert(!stack.empty() && stack[0] == u);
T flow = numeric_limits<T>::max();
for(auto u: stack){
auto &e = F.edge[pe[u]];
flow = min(flow, e.capacity - e.flow);
}
for(auto u: stack) F.add_flow(pe[u], flow);
return true;
}
break;
}
stack.push_back(u);
state[u] = 1;
if(!~pe[u]) break;
u = F.edge[pe[u]].from;
}
for(auto u: stack) state[u] = 2;
stack.clear();
}
return false;
};
for(auto qbeg = 0, iter = 0; qbeg < (int)q.size(); ++ qbeg){
int u = q[qbeg];
in_queue[u] = false;
for(auto id: F.adj[u]){
auto &e = F.edge[id];
if(e.capacity - e.flow > eps && h[u] + e.cost < h[e.to]){
h[e.to] = h[u] + e.cost;
pe[e.to] = id;
if(++ iter == F.n){
iter = 0;
if(detect_cycle()) return true;
}
if(!in_queue[e.to]){
q.push_back(e.to);
in_queue[e.to] = true;
}
}
}
}
return detect_cycle();
}
void _initialize_potential_SPFA(){
fill(h.begin(), h.end(), 0);
q.resize(F.n);
iota(q.begin(), q.end(), 0);
in_queue.assign(F.n, false);
for(auto qbeg = 0, iter = 0; qbeg < (int)q.size(); ++ qbeg){
int u = q[qbeg];
in_queue[u] = false;
for(auto id: F.adj[u]){
auto &e = F.edge[id];
if(e.capacity - e.flow > h[u] + e.cost < h[e.to]){
h[e.to] = h[u] + e.cost;
assert(++ iter < F.n); // must be negative-cycle-free
if(!in_queue[e.to]){
q.push_back(e.to);
in_queue[e.to] = true;
}
}
}
}
}
template<bool type>
T _expath(int source, int sink, T threshold){
for(auto e: F.edge) if(e.capacity - e.flow > eps) ASSERT(e.cost + h[e.from] - h[e.to] >= 0);
static const C inf = numeric_limits<C>::max();
fill(h_next.begin(), h_next.end(), inf);
h_next[source] = 0;
pe.assign(F.n, -1);
if(2 * (int)F.edge.size() * log(F.n) <= 1LL * F.n * F.n){ // Dijkstra with heap
pq.push({0, source});
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d != h_next[u]) continue;
for(auto id: F.adj[u]){
auto &e = F.edge[id];
if(e.capacity - e.flow > eps && h_next[e.to] > h_next[u] + e.cost + h[u] - h[e.to]){
pe[e.to] = id;
pq.push({h_next[e.to] = h_next[u] + e.cost + h[u] - h[e.to], e.to});
}
}
}
}
else{ // Quadratic
done.assign(F.n, false);
while(true){
int u = -1;
for(auto v = 0; v < F.n; ++ v) if(!done[v] && (!~u || h_next[u] > h_next[v])) u = v;
if(!~u) break;
done[u] = true;
for(auto id: F.adj[u]){
auto &e = F.edge[id];
if(e.capacity - e.flow > eps && h_next[e.to] > h_next[u] + e.cost + h[u] - h[e.to]){
pe[e.to] = id;
h_next[e.to] = h_next[u] + e.cost + h[u] - h[e.to];
}
}
}
}
if(!~pe[sink]) return 0;
T flow = threshold;
C cost = 0;
for(auto u = sink; u != source; ){
auto &e = F.edge[pe[u]];
flow = min(flow, e.capacity - e.flow);
cost += e.cost;
u = e.from;
}
if(type && cost > 0) return 0;
for(auto u = sink; u != source; ){
auto &e = F.edge[pe[u]];
F.add_flow(pe[u], flow);
u = e.from;
}
for(auto u = 0; u < F.n; ++ u){
if(h_next[u] == inf) h_next[u] = h[u];
else h_next[u] += h[u];
}
swap(h, h_next);
return flow;
}
// type 0: min cost max flow
// type 1: min cost flow
// O(Augmenting_Path_Count * min(n^2, n + m * log(n)))
// additional O(Cycle_Cnt * SPFA) if negative cycle exists
// additional O(SPFA) if an unsaturated edge with negative cost exists
template<bool type = false, bool negative_cycle_presence = false>
pair<T, C> solve(int source, int sink, T threshold = numeric_limits<T>::max()){
assert(0 <= min(source, sink) && max(source, sink) < F.n && source != sink && threshold >= 0);
C init_cost = F.cost;
if(negative_cycle_presence) while(_try_cycle_cancelling());
for(auto e: F.edge) if(e.flow < e.capacity && e.cost + h[e.from] - h[e.to] < 0){
_initialize_potential_SPFA();
break;
}
T flow = 0;
for(T delta; threshold > 0 && (delta = _expath<type>(source, sink, threshold)) > eps; flow += delta, threshold -= delta);
return {flow, F.cost - init_cost};
}
#undef ASSERT
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector p(n, vector<int>(m));
vector w(n, vector<int>(m));
int sum_w = 0;
rep(i, 0, n) {
rep(j, 0, m) {
cin >> p[i][j];
}
}
rep(i, 0, n) {
rep(j, 0, m) {
cin >> w[i][j];
sum_w += w[i][j];
}
}
auto room = [&](int x, int y) {
return x * m + y;
};
// n x (m + 1) of these
auto vert_wall = [&](int x, int y) {
return n * m + x * (m + 1) + y;
};
// (n + 1) x m of these
auto horz_wall = [&](int x, int y) {
return n * m + n * (m + 1) + x * m + y;
};
auto left = [&](int x, int y) { return horz_wall(x, y); };
auto right = [&](int x, int y) { return horz_wall(x, y+1); };
auto up = [&](int x, int y) { return vert_wall(x, y); };
auto down = [&](int x, int y) { return vert_wall(x+1, y); };
int src = (n * m) + (n * (m + 1)) + ((n + 1) * m);
int sink = src + 1;
flow_network_weighted<ll, ll> gr(sink + 1);
auto addEdge = [&](int a, int b, ll c, ll d) {
gr.orient(a, b, c, d);
};
rep(i, 0, n) {
rep(j, 0, m) {
addEdge(src, room(i, j), w[i][j], 0);
addEdge(room(i, j), left(i, j), 1, 0);
addEdge(room(i, j), right(i, j), 1, 0);
addEdge(room(i, j), up(i, j), 1, 0);
addEdge(room(i, j), down(i, j), 1, 0);
}
}
rep(i, 0, n) {
rep(j, 0, m+1) {
int betw_cost;
if (j > 0 && j < m) {
betw_cost = p[i][j - 1] * p[i][j];
} else {
betw_cost = 0;
}
addEdge(vert_wall(i, j), sink, 1, 0);
addEdge(vert_wall(i, j), sink, 1, betw_cost);
}
}
rep(i, 0, n+1) {
rep(j, 0, m) {
int betw_cost;
if (i > 0 && i < n) {
betw_cost = p[i - 1][j] * p[i][j];
} else {
betw_cost = 0;
}
addEdge(horz_wall(i, j), sink, 1, 0);
addEdge(horz_wall(i, j), sink, 1, betw_cost);
}
}
auto mcmf = minimum_cost_maximum_flow_johnson(gr);
cout << mcmf.solve(src, sink).second << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
4 3 1 7 10 7 2 8 7 9 10 4 6 4 3 3 3 3 2 4 4 3 4 2 2 3
output:
178
result:
ok 1 number(s): "178"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
4 3 2 2 9 9 8 4 8 4 5 7 5 2 0 1 0 1 0 1 0 0 1 0 1 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 56ms
memory: 3944kb
input:
20 20 755 344 600 54 516 407 657 429 565 185 90 323 449 464 872 138 404 500 196 111 666 191 824 98 505 538 949 801 266 861 984 957 396 851 496 147 225 451 874 380 536 200 581 397 305 514 351 416 228 763 566 442 618 131 527 651 954 757 226 129 286 608 819 477 891 22 19 747 565 704 198 703 736 8 835 1...
output:
12792427
result:
wrong answer 1st numbers differ - expected: '14347279', found: '12792427'