Submission #2407667

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e17;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(int i = 0; i < n; i++)




class ford_fulkerson{
private:
    long long inf;  // 初期化に使う値
    struct edge {
        long long to, cap, rev;
    };
    vector<vector<edge>> list;  // グラフの隣接リスト
    vector<long long> level;    // sからの距離
    vector<long long> iter;     // どこまで調べ終わったか
public:
    ford_fulkerson(long long n, long long infinity = 1e16);    // nは頂点の数、infinityは初期化に使う値
    void add_edge(long long from, long long to, long long cap); // fromからtoへ容量capの辺をはる
    void bfs(long long s);  // sからの最短距離を求める
    long long dfs(long long v, long long t, long long f);   // 増加パスをdfsで探す
    long long max_flow(long long s, long long t);   // sからtへの最大流を求める
};

ford_fulkerson::ford_fulkerson(long long n, long long infinity){
    list.resize(n);
    level.resize(n);
    iter.resize(n);
}

void ford_fulkerson::add_edge(long long from, long long to, long long cap){
    list[from].push_back((edge){to, cap, (long long)list[to].size()});
    list[to].push_back((edge){from, 0, (long long)list[from].size() - 1});
}

void ford_fulkerson::bfs(long long s){
    for(long long i = 0; i < level.size(); i++){
        level[i] = -1;
    }
    queue<long long> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        long long v = que.front(); que.pop();
        for(auto &x : list[v]){
            if(x.cap > 0 && level[x.to] < 0){
                level[x.to] = level[v] + 1;
                que.push(x.to);
            }
        }
    }
}

long long ford_fulkerson::dfs(long long v, long long t, long long f){
    if(v == t)return f;
    
    for(long long &i = iter[v]; i < list[v].size(); i++){
        edge &e = list[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            long long d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                list[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

long long ford_fulkerson::max_flow(long long s, long long t){
    long long flow = 0;
    
    for(;;){
        bfs(s);
        if(level[t] < 0)return flow;
        
        for(long long i = 0; i < iter.size(); i++){
            iter[i] = 0;
        }
        
        long long f;
        while((f = dfs(s, t, INF)) > 0){
            flow += f;
        }
    }
}

int main() {
    ll n, g, e;
    cin >> n >> g >> e;
    
    ford_fulkerson f(n + 2);
    REP(i, g){
        ll p;
        cin >> p;
        f.add_edge(p, n + 1, 1);
    }
    REP(i, e){
        int a, b;
        cin >> a >> b;
        f.add_edge(a, b, 1);
    }
    
    cout << f.max_flow(0, n + 1) << endl;
}

Submission Info

Judge Result