Submission #1293250

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstddef>
#include <cstring>
#include <numeric>
#include <vector>
#include <algorithm>
#include <queue>

// C++11-compatible FastIO
namespace FastIO{static constexpr size_t E=(1<<17);static constexpr size_t T=23
,A=334;static constexpr char O[]="%.16f";FILE*e=stdin,*t=stdout;char a[E|1],*o,
*i;char n[E|1],*s,*h;inline size_t r(){size_t g=fread(a,1,E,e);*(i=a+g)=0;o=a;
return g;}inline size_t d(){std::ptrdiff_t g=i-o;if(a+g>=o){return 0;}memcpy(a,
o,g);size_t v=fread(a+g,1,E-g,e);*(i=a+(g+=v))=0;o=a;return v;}inline void l(d\
ouble&g){if(*o==0&&r()){g=0;return;}char*b;g=strtod(o,&b);while(b==o){if(!r()){
g=0;return;}g=strtod(o,&b);}if(b==i&&d()){g=strtod(a,&b);}o=b;}inline void l(c\
har&g){if(*o==0){r();}if((g=*o)!=0){++o;}}inline void l(char*g){while(1){if(*o
==0&&!r()){*g=0;return;}if(*o<=' '){++o;}else{break;}}for(char*b=o;;++o){if(*o
==0){memcpy(g,b,o-b);g+=o-b;if(!r()){*g=0;return;}b=o;}else if(*o<=' '){memcpy(
g,b,o-b);g+=o-b;*g=0;return;}}}template<class N>inline void l(N&g,typename std
::enable_if<std::is_signed<N>::value>::type*y=0){g=0;int p=0;if(o+T>=i){d();}w\
hile(*o<'-'){++o;}if(*o=='-'){p=1;++o;}do{g=g*10+*o-'0';}while(*++o>='0');++o;
if(p){g=-g;}}template<class N>inline void l(N&g,typename std::enable_if<!std::
is_signed<N>::value>::type*y=0){g=0;if(o+T>=i){d();}while(*o<'0'){++o;}do{g=g*
10+*o-'0';}while(*++o>='0');++o;}inline void c(){while((*o!=0||r())&&*o++<=' ')
{}}inline void c(char g){while((*o!=0||r())&&*o++<=' '){}}inline void u(){fwri\
te(n,1,s-n,t);s=n;}inline void m(char g){if(s+1>=h)u();*s++=g;}inline void m(c\
onst char*g){size_t y=strlen(g);if(s+y>=h){u();}if(s+y>=h){fwrite(g,1,y,t);}el\
se{memcpy(s,g,y);s+=y;}}template<size_t N>inline void m(const char(&g)[N]){m(&g
[0]);}inline void m(double g){char y[A];size_t p=snprintf(y,A,O,g);char*b=s+p;
if(b>=h){u();b=n+p;}memcpy(s,y,p);s=b;}template<class N>inline void m(N g,type\
name std::enable_if<std::is_signed<N>::value>::type*y=0){if(s+T>=h){u();}if(g==
0){*s++='0';return;}char k[T],*j=k+T,*x=j;if(g<0){*s++='-';g=-g;}do{*--j=g%10+
'0';g/=10;}while(g);memcpy(s,j,x-j);s+=x-j;}template<class N>inline void m(N g,
typename std::enable_if<!std::is_signed<N>::value>::type*y=0){if(s+T>=h){u();}
if(g==0){*s++='0';return;}char v[T],*k=v+T,*j=k;do{*--k=g%10+'0';g/=10;}while(g
);memcpy(s,k,j-k);s+=j-k;}struct Scanner{Scanner(){o=a;i=a+E;r();}template<cla\
ss Z>inline void scan(Z&&z){l(z);}template<class Z,class...Q>inline void scan(Z
&&z,Q&&...q){l(z);scan(q...);}};struct Printer{Printer(){s=n;h=n+E;}~Printer(){
u();}template<class Z>inline void print(Z z){m(z);}template<class Z,class...Q>
inline void print(Z z,Q...q){m(z);print(q...);}template<class Z>inline void pr\
intln(Z z){m(z);m('\n');}};}

FastIO::Scanner cin;
FastIO::Printer cout;

using Weight=int;

static const Weight INF=1<<29;

struct Arc {
    // accessible to the reverse edge
    size_t src, dst;
    Weight capacity, flow;
    size_t rev;
    Arc() {}
    Arc(size_t src, size_t dst, Weight capacity):
        src(src), dst(dst), capacity(capacity), flow(0), rev(-1)
    {}
    Weight residue() const {
        return capacity - flow;
    }
};

using Arcs=std::vector<Arc>;
using Node=std::vector<Arc>;
using FlowNetwork=std::vector<Node>;

void connect(FlowNetwork &g, size_t s, size_t d, Weight c=1) {
    g[s].emplace_back(s, d, c);
    g[d].emplace_back(d, s, 0);

    g[s].back().rev = g[d].size()-1;
    g[d].back().rev = g[s].size()-1;
}

void join(FlowNetwork &g, size_t s, size_t d, Weight c=1) {
    g[s].emplace_back(s, d, c);
    g[d].emplace_back(d, s, c);

    g[s].back().rev = g[d].size()-1;
    g[d].back().rev = g[s].size()-1;
}

Weight maximum_flow(FlowNetwork &g, size_t s, size_t t) {
    /* Goldberg-Tarjan */
    size_t V=g.size();
    std::vector<size_t> d(V);
    std::vector<Weight> excess(V); excess[s]=INF;

    auto _global_relabel=[&, t]()->void {
        std::queue<size_t> q; q.push(t);
        d.assign(V, INF); d[t]=0;
        while (!q.empty()) {
            size_t u=q.front(); q.pop();
            for (Arc &e: g[u])
                if (g[e.dst][e.rev].residue()>0 && d[e.src]+1<d[e.dst]) {
                    q.push(e.dst);
                    d[e.dst] = d[e.src] + 1;
                }
        }
    };

    auto _push=[&](Arc &e)->void {
        Weight delta=std::min(excess[e.src], e.residue());
        e.flow += delta;
        excess[e.src] -= delta;
        excess[e.dst] += delta;
    };

    _global_relabel();
    if (d[s] >= INF) return 0;

    std::vector<std::queue<size_t>> B(V); B[d[s]].push(s);
    for (size_t b=d[s], count_=0; ~b; ++count_) {
        if (B[b].empty()) {
            --b;
            continue;
        }

        size_t v=B[b].front(); B[b].pop();
        if (!excess[v] || v==t) continue;

        for (Arc &e: g[v]) {
            size_t w=e.dst;
            if (e.residue()>0 && d[v]==d[w]+1) {
                _push(e);
                if (excess[w]>0 && w!=t)
                    B[d[w]].push(w);
            }
        }

        if (!excess[v]) continue;
        d[v] = V;
        for (Arc &e: g[v])
            if (e.residue() > 0)
                d[e.src] = std::min(d[e.src], d[e.dst]+1);

        if (d[v] < V) B[b=d[v]].push(v);
        if (!((++count_)%=V>>1|1)) _global_relabel();
    }
    return excess[t];
}

int main() {
    size_t N;
    int G, E;
    cin.scan(N, G, E);

    FlowNetwork g(N+1);
    for (int i=0; i<G; ++i) {
        size_t p;
        cin.scan(p);
        connect(g, p, N);
    }

    for (int i=0; i<E; ++i) {
        size_t a, b;
        cin.scan(a, b);
        join(g, a, b);
    }

    cout.println(maximum_flow(g, 0, N));
    return 0;
}

Submission Info

Judge Result