QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431819#3179. Cordon BleujuancsTL 17ms3864kbC++203.0kb2024-06-06 09:25:022024-06-06 09:25:03

Judging History

This is the latest submission verdict.

  • [2024-06-06 09:25:03]
  • Judged
  • Verdict: TL
  • Time: 17ms
  • Memory: 3864kb
  • [2024-06-06 09:25:02]
  • Submitted

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 ...

output:


result: