Submission #1293413

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

template <class T>
using less_queue=std::priority_queue<T, std::deque<T>, std::greater<T>>;

struct SimpleEdge {
    size_t src, dst;
    SimpleEdge(size_t src, size_t dst): src(src), dst(dst) {}
};

template <class Weight>
struct WeightedEdge {
    using weight_type=Weight;
    size_t src, dst;
    Weight cost;
    WeightedEdge(size_t src, size_t dst, Weight cost):
        src(src), dst(dst), cost(cost)
    {}
};

template <class Weight>
struct FlowArc {
    using weight_type=Weight;
    size_t src, dst, rev;
    Weight cost, capacity, flow;
    FlowArc(size_t src, size_t dst, size_t rev, Weight cost, Weight capacity):
        src(src), dst(dst), rev(rev), cost(cost), capacity(capacity), flow(0)
    {}
    Weight residue() const {
        return capacity - flow;
    }
};

template <class EdgeType>
struct Graph: public std::vector<std::vector<EdgeType>> {
    using edge_type=EdgeType;
    Graph(size_t v): std::vector<std::vector<EdgeType>>(v) {}
    template <class... Attrs>
    void connect_d(size_t src, size_t dst, Attrs ...attrs) {
        (*this)[src].emplace_back(src, dst, attrs...);
    }
    template <class... Attrs>
    void connect_u(size_t src, size_t dst, Attrs ...attrs) {
        (*this)[src].emplace_back(src, dst, attrs...);
        (*this)[dst].emplace_back(dst, src, attrs...);
    }
    template <class Weight=typename EdgeType::weight_type>
    void connect_dr(size_t src, size_t dst, Weight cost, Weight capacity) {
        size_t rev_s=(*this)[dst].size();
        size_t rev_d=(*this)[src].size();
        (*this)[src].emplace_back(src, dst, rev_s, cost, capacity);
        (*this)[dst].emplace_back(dst, src, rev_d, 0, -capacity);
    }
    template <class... Attrs>
    void connect_ur(size_t src, size_t dst, Attrs ...attrs) {
        size_t rev_s=(*this)[dst].size();
        size_t rev_d=(*this)[src].size();
        (*this)[src].emplace_back(src, dst, rev_s, attrs...);
        (*this)[dst].emplace_back(dst, src, rev_d, attrs...);
    }
};

template <class Weight>
struct FlowNetwork: public Graph<FlowArc<Weight>> {
    static const Weight INF=std::numeric_limits<Weight>::max()/4;
    FlowArc<Weight> &reversed(FlowArc<Weight> &e) {
        return (*this)[e.dst][e.rev];
    }
    FlowArc<Weight> &reversed(FlowArc<Weight> *e) {
        return (*this)[e->dst][e->rev];
    }
    FlowNetwork(size_t v): Graph<FlowArc<Weight>>(v) {}
    std::pair<Weight, Weight> mincflow(
        size_t src, size_t snk, Weight fbound=INF
    ) {
        size_t size=this->size();
        std::vector<Weight> pot(size);
        Weight maxflow=0, mincost=0;
        while (fbound > maxflow) {
            std::vector<Weight> d(size, INF);
            d[src] = 0;
            std::vector<FlowArc<Weight> *> prev(size, nullptr);
            less_queue<std::pair<Weight, size_t>> q;
            q.emplace(0, src);
            while (!q.empty()) {
                std::pair<Weight, size_t> p=q.top();
                q.pop();
                size_t v=p.second;
                if (d[v] < p.first) continue;

                for (FlowArc<Weight> &e: (*this)[v]) {
                    if (e.residue() <= 0) continue;

                    Weight cur=(d[e.src]+e.cost)+(pot[e.src]-pot[e.dst]);
                    if (d[e.dst] > cur) {
                        d[e.dst] = cur;
                        prev[e.dst] = &e;
                        q.emplace(d[e.dst], e.dst);
                    }
                }
            }

            if (d[snk] == INF) break;

            for (size_t v=0; v<size; ++v)
                pot[v] += d[v];

            Weight f=fbound-maxflow;
            for (FlowArc<Weight> *e=prev[snk]; e!=nullptr; e=prev[e->src])
                f = std::min(f, e->residue());

            maxflow += f;
            mincost += f * pot[snk];
            for (FlowArc<Weight> *e=prev[snk]; e!=nullptr; e=prev[e->src]) {
                e->flow += f;
                reversed(e).flow -= f;
            }
        }

        return {maxflow, mincost};
    }
    Weight maxflow(size_t src, size_t snk, Weight fbound=INF) {
        size_t size=this->size();
        std::vector<Weight> pot(size);
        Weight maxflow=0;
        while (fbound > maxflow) {
            std::vector<Weight> d(size, INF);
            d[src] = 0;
            std::vector<FlowArc<Weight> *> prev(size, nullptr);
            less_queue<std::pair<Weight, size_t>> q;
            q.emplace(0, src);
            while (!q.empty()) {
                std::pair<Weight, size_t> p=q.top();
                q.pop();
                size_t v=p.second;
                if (d[v] < p.first) continue;

                for (FlowArc<Weight> &e: (*this)[v]) {
                    if (e.residue() <= 0) continue;

                    Weight cur=(d[e.src]+e.cost)+(pot[e.src]-pot[e.dst]);
                    if (d[e.dst] > cur) {
                        d[e.dst] = cur;
                        prev[e.dst] = &e;
                        q.emplace(d[e.dst], e.dst);
                    }
                }
            }

            if (d[snk] == INF) break;

            for (size_t v=0; v<size; ++v)
                pot[v] += d[v];

            Weight f=fbound-maxflow;
            for (FlowArc<Weight> *e=prev[snk]; e!=nullptr; e=prev[e->src])
                f = std::min(f, e->residue());

            maxflow += f;
            for (FlowArc<Weight> *e=prev[snk]; e!=nullptr; e=prev[e->src]) {
                e->flow += f;
                reversed(e).flow -= f;
            }
        }

        return maxflow;
    }
};

int main() {
    size_t N;
    int G, E;
    scanf("%zu %d %d", &N, &G, &E);

    FlowNetwork<int> g(N+1);
    for (int i=0; i<G; ++i) {
        size_t p;
        scanf("%zu", &p);
        g.connect_dr(p, N, 0, 1);
    }

    for (int i=0; i<E; ++i) {
        size_t a, b;
        scanf("%zu %zu", &a, &b);
        g.connect_ur(a, b, 0, 1);
    }

    printf("%d\n", g.maxflow(0, N));
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:177:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%zu %d %d", &N, &G, &E);
                                   ^
./Main.cpp:182:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%zu", &p);
                         ^
./Main.cpp:188:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%zu %zu", &a, &b);
                                 ^

Judge Result