QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173072#7185. Poor Studentsucup-team139#TL 3392ms7068kbC++233.4kb2023-09-09 21:51:132023-09-09 21:51:13

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 21:51:13]
  • 评测
  • 测评结果:TL
  • 用时:3392ms
  • 内存:7068kb
  • [2023-09-09 21:51:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vpi = V<pair<int,int>>;
#define sz(x) int((x).size())
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define each(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set $a = \min(a,b)$

struct MCMF { // 0-based, archi direzionati
    using F = int; using C = ll; // flow type, cost type
    struct Edge { int to, rev; F flo, cap; C cost; };
    int N; V<C> p, dist; vpi pre; V<V<Edge>> adj;
    void init(int _N) { N = _N;
        p.resize(N),adj.resize(N),dist.resize(N),pre.resize(N);}
    void ae(int u, int v, F cap, C cost) { assert(cap >= 0); 
        adj[u].pb({v,sz(adj[v]),0,cap,cost}); 
        adj[v].pb({u,sz(adj[u])-1,0,0,-cost});
    }
    //send flow through lowest cost path
    bool path(int s, int t) {
        const C inf = numeric_limits<C>::max(); 
        dist.assign(N,inf);
        using T = pair<C,int>;
        queue<T> todo;//(or queue<T>)
        todo.push({dist[s] = 0,s}); 
        while (sz(todo)) { // Dijkstra (or SPFA)
            T x = todo.front(); todo.pop(); //(or todo.front())
            if (x.f > dist[x.s]) x.f = dist[x.s]; //(or x.f = dist[x.s])
            //all weights should be non-negative
            each(e,adj[x.s]) {
                if (e.flo < e.cap && ckmin(dist[e.to],
                    x.f+e.cost+p[x.s]-p[e.to])) {
                    pre[e.to]={x.s,e.rev};
                    todo.push({dist[e.to],e.to});
                }
            }
        } // if costs are doubles, add some EPS so you 
        // don't traverse ~0-weight cycle repeatedly
        return dist[t] != inf; // true if augmenting path
    }
    pair<F,C> calc(int s, int t) { assert(s != t);
        F0R(_,5)F0R(i,N)each(e,adj[i])//utile con grafi densi...
          if(e.cap)ckmin(p[e.to],p[i]+e.cost);//e archi negativi
        F totFlow = 0; C totCost = 0;
        while (path(s,t)) { // p -> potentials for Dijkstra
            F0R(i,N)p[i]+=dist[i];//don't matter for unreachable
            F df = numeric_limits<F>::max();
            for (int x = t; x != s; x = pre[x].f) {
                Edge& e = adj[pre[x].f][adj[x][pre[x].s].rev]; 
                ckmin(df,e.cap-e.flo); }
            totFlow += df; totCost += (p[t]-p[s])*df;
            for (int x = t; x != s; x = pre[x].f) {
                Edge& e = adj[x][pre[x].s]; e.flo -= df;
                adj[pre[x].f][e.rev].flo += df;
            }
        } // get max flow you can send along path
        return {totFlow,totCost};
    }
};

void solve(int t){
    int n,k;
    cin>>n>>k;
    
    MCMF ds;
    int source = n+k, sink = n+k+1;
    ds.init(n+k+2);
    
    for(int i=0;i<n;i++){
        ds.ae(source,i,1,0);
        for(int j=0;j<k;j++){
            int c;
            cin>>c;
            ds.ae(i,n+j,1,c);
        }
    }
    
    for(int i=0;i<k;i++){
        int a;
        cin>>a;
        ds.ae(n+i,sink,a,0);
    }
    
    cout<<ds.calc(source,sink).second<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3500kb

input:

6 2
1 2
1 3
1 4
1 5
1 6
1 7
3 4

output:

12

result:

ok answer is '12'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

3 3
1 2 3
2 4 6
6 5 4
1 1 1

output:

8

result:

ok answer is '8'

Test #3:

score: 0
Accepted
time: 101ms
memory: 4196kb

input:

1000 10
734 303 991 681 755 155 300 483 702 442
237 256 299 675 671 757 112 853 759 233
979 340 288 377 718 199 935 666 576 842
537 363 592 349 494 961 864 727 84 813
340 78 600 492 118 421 478 925 552 617
517 589 716 7 928 638 258 297 706 787
266 746 913 978 436 859 701 951 137 44
815 336 471 720 2...

output:

92039

result:

ok answer is '92039'

Test #4:

score: 0
Accepted
time: 3392ms
memory: 7068kb

input:

5000 10
14 114 254 832 38 904 25 147 998 785
917 694 750 372 379 887 247 817 999 117
802 15 799 515 316 42 69 247 95 144
727 398 509 725 682 456 369 656 693 955
923 1 681 631 962 826 233 963 289 856
165 491 488 832 111 950 853 791 929 240
509 843 667 970 469 260 447 477 161 431
514 903 627 236 144 3...

output:

461878

result:

ok answer is '461878'

Test #5:

score: -100
Time Limit Exceeded

input:

10000 10
307 205 765 487 504 526 10 581 234 583
448 443 39 992 976 363 335 588 588 169
920 787 896 822 47 358 230 631 136 299
141 159 414 852 922 945 513 76 111 189
616 104 83 792 24 68 164 975 615 472
150 108 848 517 7 153 107 283 452 165
94 370 910 662 226 720 975 214 324 407
636 65 963 859 590 3 ...

output:


result: