Submission #1461345

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using llng = long long;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T> >;

struct Edge {
    int to, cap, rev;
    Edge(int _t, int _c, int _r) : to(_t), cap(_c), rev(_r) {}
};

struct Graph {
    vv<Edge> edge;
    Graph(int N) { edge = vv<Edge>(N); }
    void add(int from, int to, int cap) { add_edge(from, to, cap, false); }
    void add_ud(int v1, int v2, int cap) { add_edge(v1, v2, cap, true); }
private:
    void add_edge(int v1, int v2, int cap, bool isUd) {
        int v1_rev = edge[v2].size();
        int v2_rev = edge[v1].size();
        edge[v1].push_back(Edge(v2, cap, v1_rev));
        edge[v2].push_back(Edge(v1, (isUd ? cap : 0), v2_rev));
    }
};

class FF {
    Graph g;
    v<bool> used;
    int ff_dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (Edge &e : g.edge[v]) if (!used[e.to] && e.cap > 0) {
            int d = ff_dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d; g.edge[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
public:
    FF(Graph _g) : g(_g) {}
    int run(int s, int t) {
        int fl = 0;
        while (true) {
            used = v<bool>(g.edge.size());
            int f = ff_dfs(s, t, 1e9);
            if (f == 0) return fl;
            fl += f;
        }
    }
};

int main() {
    int N, G, E; cin >> N >> G >> E;
    Graph g(N+1);
    for (int i=0; i<G; i++) { int p; cin >> p; g.add(p, N, 1); }
    for (int i=0; i<E; i++) { int a, b; cin >> a >> b; g.add_ud(a, b, 1); }
    cout << FF(g).run(0, N) << endl;
    return 0;
}

Submission Info

Judge Result