QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#431819 | #3179. Cordon Bleu | juancs | TL | 17ms | 3864kb | C++20 | 3.0kb | 2024-06-06 09:25:02 | 2024-06-06 09:25:03 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i >= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
struct edge{
int to, rev; ll cap, cos, f{0};
edge(int to, int rev, ll cap, ll cos):to(to), rev(rev), cap(cap), cos(cos){}
};
struct MCMF{
int n, s, t;
vector<vector<edge>> g;
vi p; vll dis;
MCMF(int n): n(n), g(n){}
void addEdge(int s, int t, ll cap, ll cos){
g[s].pb(edge(t, sz(g[t]), cap, cos));
g[t].pb(edge(s, sz(g[s])-1, 0, -cos));
}
void spfa(int v0){
dis.assign(n, inf); dis[v0] = 0;
p.assign(n, -1);
vector<bool> inq(n);
queue<int> q({v0});
while(sz(q)){
int u = q.front(); q.pop();
inq[u] = 0;
for(auto&[v, rev, cap, cos, f] : g[u]){
if(cap - f > 0 && dis[v] > dis[u] + cos){
dis[v] = dis[u] + cos, p[v] = rev;
if(!inq[v]) inq[v] = 1, q.push(v);
}
}
}
}
ll min_cos_flow(ll K){
ll flow = 0, cost = 0;
while(flow < K){
spfa(s);
if(dis[t] == inf) break;
ll f = K - flow;
int cur = t; // Find flow
while(cur != s){
int u = g[cur][p[cur]].to, rev = g[cur][p[cur]].rev;
f = min(f, g[u][rev].cap - g[u][rev].f);
cur = u;
}
flow += f, cost += f * dis[t], cur = t; // Apply flow
while(cur != s){
int u = g[cur][p[cur]].to, rev = g[cur][p[cur]].rev;
g[u][rev].f += f, g[cur][p[cur]].f -= f;
cur = u;
}
}
if(flow < K) assert(0);
return cost;
}
};
struct pt{
int x, y;
pt(){}
pt(int x, int y): x(x), y(y){}
ll dst(pt p){return abs(x - p.x) + abs(y - p.y); }
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.precision(21);
int n, m;
cin >> m >> n;
vector<pt> crs(n), wn(m);
forn(j, m)cin >> wn[j].x >> wn[j].y;
forn(i, n)cin >> crs[i].x >> crs[i].y;
pt rst = pt();
cin >> rst.x >> rst.y;
int N = n + m + 3;
MCMF flw = MCMF(N);
flw.s = 0;
flw.t = 1;
forn(i, n){
flw.addEdge(0, i + 3, 1, 0);
}
flw.addEdge(0, 2, m - 1, 0);
forn(i, n){
forn(j, m){
flw.addEdge(i + 3, j + n + 3, 1, crs[i].dst(wn[j]));
}
}
forn(j, m){
flw.addEdge(2, j + n + 3, 1, rst.dst(wn[j]));
}
forn(j, m){
flw.addEdge(j + n + 3, 1, 1, rst.dst(wn[j]));
}
ll ans = flw.min_cos_flow(m);
cout << ans << el;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
input:
1 1 -324 -832 -324 -832 -324 -832
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3472kb
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: 1ms
memory: 3468kb
input:
1 1 597 546 -353 -842 597 546
output:
2338
result:
ok single line: '2338'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1 1 -224 757 122 562 122 562
output:
1082
result:
ok single line: '1082'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3568kb
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: 3780kb
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: 3576kb
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: 3468kb
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: 3720kb
input:
1 1 -19 106 -407 -746 -837 935
output:
2887
result:
ok single line: '2887'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3728kb
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: 0
Accepted
time: 17ms
memory: 3864kb
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:
3067457
result:
ok single line: '3067457'
Test #12:
score: -100
Time Limit Exceeded
input:
1000 1000 -184 402 590 -350 -240 949 -28 -995 901 -709 228 -865 -771 861 -545 -734 643 -978 499 199 -817 358 211 877 143 -220 -568 932 -724 -357 -527 305 347 -634 286 848 184 -706 -821 -793 -907 341 -594 -626 -850 971 -969 933 191 -559 -511 894 -505 36 75 -988 749 409 800 113 -545 -771 376 -983 549 ...