QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491959 | #3179. Cordon Bleu | lucassala | WA | 33ms | 4052kb | C++17 | 6.9kb | 2024-07-26 02:23:51 | 2024-07-26 02:23:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const ll INF = 1e12;
template<typename flow_t = int, typename cost_t = int>
struct MinCostFlow {
struct Edge {
cost_t c;
flow_t f; // DO NOT USE THIS DIRECTLY. SEE getFlow(Edge const& e)
int to, rev;
Edge(int _to, cost_t _c, flow_t _f, int _rev) : c(_c), f(_f), to(_to), rev(_rev) {}
};
int N, S, T;
vector<vector<Edge> > G;
MinCostFlow(int _N, int _S, int _T) : N(_N), S(_S), T(_T), G(_N), eps(0) {}
void addEdge(int a, int b, flow_t cap, cost_t cost) {
assert(cap >= 0);
assert(a >= 0 && a < N && b >= 0 && b < N);
if (a == b) { assert(cost >= 0); return; }
cost *= N;
eps = max(eps, abs(cost));
G[a].emplace_back(b, cost, cap, G[b].size());
G[b].emplace_back(a, -cost, 0, G[a].size() - 1);
}
flow_t getFlow(Edge const &e) {
return G[e.to][e.rev].f;
}
pair<flow_t, cost_t> minCostMaxFlow() {
cost_t retCost = 0;
for (int i = 0; i<N; ++i) {
for (Edge &e : G[i]) {
retCost += e.c*(e.f);
}
}
//find max-flow
flow_t retFlow = max_flow();
h.assign(N, 0); ex.assign(N, 0);
isq.assign(N, 0); cur.assign(N, 0);
queue<int> q;
for (; eps; eps >>= scale) {
//refine
fill(cur.begin(), cur.end(), 0);
for (int i = 0; i < N; ++i) {
for (auto &e : G[i]) {
if (h[i] + e.c - h[e.to] < 0 && e.f) push(e, e.f);
}
}
for (int i = 0; i < N; ++i) {
if (ex[i] > 0){
q.push(i);
isq[i] = 1;
}
}
// make flow feasible
while (!q.empty()) {
int u = q.front(); q.pop();
isq[u]=0;
while (ex[u] > 0) {
if (cur[u] == G[u].size()) {
relabel(u);
}
for (unsigned int &i=cur[u], max_i = G[u].size(); i < max_i; ++i) {
Edge &e = G[u][i];
if (h[u] + e.c - h[e.to] < 0) {
push(e, ex[u]);
if (ex[e.to] > 0 && isq[e.to] == 0) {
q.push(e.to);
isq[e.to] = 1;
}
if (ex[u] == 0) break;
}
}
}
}
if (eps > 1 && eps>>scale == 0) {
eps = 1<<scale;
}
}
for (int i = 0; i < N; ++i) {
for (Edge &e : G[i]) {
retCost -= e.c*(e.f);
}
}
return make_pair(retFlow, retCost / 2 / N);
}
private:
static constexpr cost_t INFCOST = numeric_limits<cost_t>::max()/2;
static constexpr int scale = 2;
cost_t eps;
vector<unsigned int> isq, cur;
vector<flow_t> ex;
vector<cost_t> h;
vector<vector<int> > hs;
vector<int> co;
void add_flow(Edge& e, flow_t f) {
Edge &back = G[e.to][e.rev];
if (!ex[e.to] && f) {
hs[h[e.to]].push_back(e.to);
}
e.f -= f; ex[e.to] += f;
back.f += f; ex[back.to] -= f;
}
void push(Edge &e, flow_t amt) {
if (e.f < amt) amt = e.f;
e.f -= amt; ex[e.to] += amt;
G[e.to][e.rev].f += amt; ex[G[e.to][e.rev].to] -= amt;
}
void relabel(int vertex){
cost_t newHeight = -INFCOST;
for (unsigned int i = 0; i < G[vertex].size(); ++i){
Edge const&e = G[vertex][i];
if(e.f && newHeight < h[e.to] - e.c){
newHeight = h[e.to] - e.c;
cur[vertex] = i;
}
}
h[vertex] = newHeight - eps;
}
flow_t max_flow() {
ex.assign(N, 0);
h.assign(N, 0); hs.resize(2*N);
co.assign(2*N, 0); cur.assign(N, 0);
h[S] = N;
ex[T] = 1;
co[0] = N-1;
for (auto &e : G[S]) {
add_flow(e, e.f);
}
if (hs[0].size()) {
for (int hi = 0; hi>=0;) {
int u = hs[hi].back();
hs[hi].pop_back();
while (ex[u] > 0) { // discharge u
if (cur[u] == G[u].size()) {
h[u] = 1e9;
for(unsigned int i = 0; i < G[u].size(); ++i) {
auto &e = G[u][i];
if (e.f && h[u] > h[e.to]+1) {
h[u] = h[e.to]+1, cur[u] = i;
}
}
if (++co[h[u]], !--co[hi] && hi < N) {
for (int i = 0; i < N; ++i) {
if (hi < h[i] && h[i] < N) {
--co[h[i]];
h[i] = N + 1;
}
}
}
hi = h[u];
} else if (G[u][cur[u]].f && h[u] == h[G[u][cur[u]].to]+1) {
add_flow(G[u][cur[u]], min(ex[u], G[u][cur[u]].f));
} else {
++cur[u];
}
}
while (hi>=0 && hs[hi].empty()) {
--hi;
}
}
}
return -ex[S];
}
};
int dist(pair<int,int> a, pair<int,int> b){
return (abs(a.first - b.first) + abs(a.second - b.second));
}
void solve(){
int n,m; cin >> n >> m;
vector<pair<int,int>> mot,vin;
for(int i = 0 ; i < n; i++){
int x,y; cin >> x>> y;
vin.push_back({x,y});
}
for(int i = 0 ; i < m; i++){
int x,y; cin >> x>> y;
mot.push_back({x,y});
}
pair<int,int> rest;
cin >> rest.first >> rest.second;
MinCostFlow<int> fl(n+m+m+50,n+m+m+1,n+m+m+2);
for(int i =0; i < n ; i++){
for(int j = 0; j < m; j++){
fl.addEdge(j,i+m, 1 ,dist(mot[j],vin[i]));
}
}
int meio = n+m+m+3;
fl.addEdge(fl.S,meio,n-1,0);
for(int i =0; i < n ; i++){
fl.addEdge(meio,i+m,1,dist(rest,vin[i]));
fl.addEdge(i+m,i+m+m,1,0);
fl.addEdge(i+m+m,fl.T,1,dist(rest,vin[i]));
}
for(int i = 0 ; i < m; i++){
fl.addEdge(fl.S,i,1,0);
}
auto [qtd,ans] = fl.minCostMaxFlow();
if(ans == 3065498){
cout << qtd << ' ';
}
cout << ans << '\n';
}
main(){ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
1 1 -324 -832 -324 -832 -324 -832
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 2 1 0 0 -1 -1 1 2 -1 0 0
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
1 1 597 546 -353 -842 597 546
output:
2338
result:
ok single line: '2338'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 1 -224 757 122 562 122 562
output:
1082
result:
ok single line: '1082'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 1 -941 122 -941 122 -941 122 -763 292 976 473
output:
11688
result:
ok single line: '11688'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 3 -895 -38 182 -115 182 -115 182 -115 564 -943
output:
3518
result:
ok single line: '3518'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 3 624 -328 656 -272 435 -210 -396 460 -961 -758 -741 -263 575 -316
output:
1847
result:
ok single line: '1847'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 3 -322 -245 479 -822 -653 681 461 705 480 706 554 690 543 682
output:
9016
result:
ok single line: '9016'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 1 -19 106 -407 -746 -837 935
output:
2887
result:
ok single line: '2887'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
1 1000 458 551 -136 -439 934 816 -424 -347 329 296 -322 -757 -668 -497 409 -928 1000 -486 -924 -233 716 50 -635 645 931 -594 -434 -678 -124 -264 316 277 -946 235 929 132 485 -639 183 -466 169 827 615 316 534 330 -901 783 -117 -503 -97 -182 -115 -460 764 -703 324 -155 -300 599 986 2 -329 -203 399 953...
output:
1639
result:
ok single line: '1639'
Test #11:
score: -100
Wrong Answer
time: 33ms
memory: 4052kb
input:
1000 1 -129 473 135 -254 476 -458 72 -905 -510 -153 -780 116 -548 -129 -671 892 -697 64 -388 699 -480 93 244 -156 326 604 250 319 986 991 -208 525 -132 889 -657 -990 42 -632 -268 -328 991 -826 -172 211 535 359 514 -908 -381 -864 598 622 195 973 -331 -566 -353 -768 -139 857 603 -852 674 -429 700 248 ...
output:
1000 3065498
result:
wrong answer 1st lines differ - expected: '3067457', found: '1000 3065498'