test/AOJ/3297.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3297

Depends on

• build/pch/stdc++.hpp
• library/flow/NondecreasingMCF.hpp
• library/graph/WeightedGraph.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3297"
#include <bits/stdc++.h>

#include "library/flow/NondecreasingMCF.hpp"

using ll = long long;
const __int128 LINF = 1e20;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    while (std::cin >> n >> m >> k, n) {
        NondecreasingMCF<__int128> fl(n);
        for (int i = 0; i < m; i++) {
            ll s, t, c, d;
            std::cin >> s >> t >> c >> d;
            s--;
            t--;
            fl.add_arc(s, t, k,
                       [c, d](int x) { return c + (x ? x * d : -LINF); });
        }
        auto [ans, ok] = fl.flow(0, n - 1, k);
        ans += LINF * m;
        std::cout << (ans < LINF ? ll(ans) : -1LL) << "\n";
    }
}

#line 1 "test/AOJ/3297.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3297"
#include <bits/stdc++.h>

#line 2 "library/flow/NondecreasingMCF.hpp"
// 辺の重みが流量に対して単調増加な関数
// 現在の流量を引数として、そこに新たに 1 流す時にかかるコストを返す関数を渡す
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
    WeightedEdge() = default;
    WeightedEdge(int from, int to, T weight)
        : from(from), to(to), weight(weight) {}
    int from, to;
    T weight;
    operator int() const { return to; }
};

template <typename T> struct WeightedGraph {
    int n;
    using weight_type = T;
    using edge_type = WeightedEdge<T>;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        WeightedGraph *g;
        int l, r;

      public:
        OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const WeightedGraph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
            : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
    WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to, T weight) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to, weight);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v, T weight) {
        add_arc(u, v, weight);
        add_arc(v, u, weight);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            T weight;
            std::cin >> weight;
            if (directed)
                add_arc(u, v, weight);
            else
                add_edge(u, v, weight);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __DEBUG
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << "(" << edges[i].to << "," << edges[i].weight
                          << ")";
            std::cerr << "\n";
        }
    }
};
#line 5 "library/flow/NondecreasingMCF.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename TC> class NondecreasingMCF {
    using F = std::function<TC(int)>;
    struct EdgeInfo {
        int cap, flow, rev;
        bool reverse_edge;
        F cost_func;

        EdgeInfo() = default;
        EdgeInfo(int cap, F cost_func, int rev, bool reverse_edge)
            : cap(cap), cost_func(cost_func), rev(rev),
              reverse_edge(reverse_edge), flow(0) {}

        TC cost() const {
            if (!reverse_edge)
                return cost_func(flow);
            return -cost_func(cap - 1);
        }
    };
    int n;
    WeightedGraph<EdgeInfo> G;
    std::vector<TC> potential, dist;
    static constexpr TC INF = std::is_same_v<TC, __int128>
                                  ? TC(1e30)
                                  : std::numeric_limits<TC>::max() / 2;
    //  std::numeric_limits<__int128 >::max() は AOJ でバグった
    std::vector<std::pair<int, int>> pre; // pre[v]=[u,i] : G[u][i] で v に来た
    std::vector<int> in_deg, out_deg;
    std::priority_queue<std::pair<TC, int>, std::vector<std::pair<TC, int>>,
                        std::greater<std::pair<TC, int>>>
        que;
    bool negative = false; // 負辺存在するか

    template <typename T> bool chmin(T &a, const T &b) {
        return (a > b and (a = b, true));
    }
    bool SP_update(int from, int edge_id) {
        const auto &e = G[from][edge_id];
        if ((e.weight).cap == 0)
            return false;
        if (chmin(dist[e.to], dist[from] + (e.weight).cost() + potential[from] -
                                  potential[e.to])) {
            pre[e.to] = {from, edge_id};
            return true;
        }
        return false;
    }

    void dijkstra(int s) { // dist[i]:sから残余グラフで辺の重みによるiへの最短路
                           // となるようにdistを作る
        std::ranges::fill(dist, INF);
        dist[s] = 0;
        que.emplace(0, s);
        while (que.size()) {
            const auto [now, v] = que.top();
            que.pop();
            if (dist[v] < now)
                continue;
            REP_(i, G[v].size())
            if (SP_update(v, i))
                que.emplace(dist[G[v][i].to], G[v][i].to);
        }
    }

    void DAG(int s) {
        negative = false;
        std::ranges::fill(dist, INF);
        dist[s] = 0;
        std::queue<int> que;
        REP_(i, n) if (!in_deg[i]) que.push(i);
        while (que.size()) {
            int v = que.front();
            que.pop();
            REP_(i, G[v].size()) {
                SP_update(v, i);
                if (!--in_deg[G[v][i].to])
                    que.push(G[v][i].to);
            }
        }
    }

  public:
    NondecreasingMCF() {}
    NondecreasingMCF(int n_)
        : n(n_), G(n_), potential(n_, 0), dist(n_), pre(n_), in_deg(n_, 0),
          out_deg(n_, 0), negative(false) {}

    void add_arc(int u, int v, int cap, F cost_func) {
        G.add_arc(u, v, {cap, cost_func, out_deg[v], false});
        G.add_arc(v, u, {0, cost_func, out_deg[u], true});
        out_deg[v]++;
        out_deg[u]++;
        if (cap > 0) {
            in_deg[v]++;
            negative |= cost_func(0) < 0;
        }
    }

    std::pair<TC, bool> flow(int s, int t, int f) {
        if (!G.is_prepared())
            G.build();
        TC res = 0;
        std::ranges::fill(potential, 0);
        for (int i = 0; i < f; i++) {
            if (negative)
                DAG(s);
            else
                dijkstra(s);
            if (dist[t] == INF)
                return std::make_pair(res, false);
            REP_(v, n) if (dist[v] != INF) potential[v] += dist[v];
            res += potential[t];
            for (int v = t; v != s; v = pre[v].first) {
                auto &w = G[pre[v].first][pre[v].second].weight;
                w.cap--;
                w.flow++;
                auto &r = G[v][w.rev].weight;
                r.cap++;
                r.flow--;
            }
        }
        return std::make_pair(res, true);
    }
};
#undef REP_
#line 5 "test/AOJ/3297.test.cpp"

using ll = long long;
const __int128 LINF = 1e20;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    while (std::cin >> n >> m >> k, n) {
        NondecreasingMCF<__int128> fl(n);
        for (int i = 0; i < m; i++) {
            ll s, t, c, d;
            std::cin >> s >> t >> c >> d;
            s--;
            t--;
            fl.add_arc(s, t, k,
                       [c, d](int x) { return c + (x ? x * d : -LINF); });
        }
        auto [ans, ok] = fl.flow(0, n - 1, k);
        ans += LINF * m;
        std::cout << (ans < LINF ? ll(ans) : -1LL) << "\n";
    }
}

Back to top page