QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#431818 | #3179. Cordon Bleu | juancs | RE | 0ms | 3720kb | C++20 | 3.0kb | 2024-06-06 09:24:03 | 2024-06-06 09:24: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, n - 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: 0ms
memory: 3536kb
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: 0ms
memory: 3720kb
input:
1 1 597 546 -353 -842 597 546
output:
2338
result:
ok single line: '2338'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 1 -224 757 122 562 122 562
output:
1082
result:
ok single line: '1082'
Test #5:
score: -100
Runtime Error
input:
3 1 -941 122 -941 122 -941 122 -763 292 976 473