Submission #6000800

---

Source Code Expand

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

struct Dinic{
    struct edge {
        int64_t to, cap, rev;
        edge(int64_t to, int64_t cap, int64_t rev):to(to), cap(cap), rev(rev){}
    };

    int N, S, T;
    int64_t flow = 0;
    const int64_t INF = 1e18;
    vector<int> level, iter;
    vector<vector<edge>> G;

    Dinic(int N, int S, int T):N(N), S(S), T(T){
        flow = 0;
        level.resize(N);
        iter.resize(N);
        G.resize(N);
    }

    void add_edge(int from, int to, int64_t cap){
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, 0, G[from].size()-1);
    }

    void bfs(int s){
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(que.size()){
            int v = que.front(); que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int64_t dfs(int v, int t, int64_t f){
        if(v == t) return f;
        for(int& i=iter[v]; i<G[v].size(); i++){
            auto& e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int64_t d = dfs(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int64_t max_flow(){
        while(true){
            bfs(S);
            if(level[T] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            while(true){
                int64_t f = dfs(S, T, INF);
                if(f == 0) break;
                flow += f;
            }
        }
    }
};

int main(){
    int N, M[300], X[300];
    cin >> N;
    for(int i=0; i<N; i++) cin >> M[i] >> X[i];

    int64_t fix = 0;
    int S = 300, T = 301;
    Dinic solver(T+1, S, T);
    for(int i=0; i<N; i++){
        if(X[i] > 0){
            fix += X[i];
            solver.add_edge(S, i, 0);
            solver.add_edge(i, T, X[i]);
        }else{
            solver.add_edge(S, i, -X[i]);
            solver.add_edge(i, T, 0);
        }
    }

    const int64_t INF = 1e15;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        if(i != j && M[i] % M[j] == 0){
            solver.add_edge(j, i, INF);
        }
    }

    int64_t ans = fix - solver.max_flow();
    cout << ans << endl;
}

Submission Info

Judge Result