zoj2930

各点向S连推迟的花费，向T连提前的花费，S表示提前，T表示推迟。a推迟b也推迟b往a连INF。最小割后从各点出发，能直接或间接到T的就是必须推迟的，剩下的就是能提前的。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=,APB=,one=,INF=0x7FFFFFFF,mod=;

int n,m,S=,T=,mp[SZ][SZ];

int dep[SZ];

void init()

{

    for(int i=;i<=n;++i)

    {

        int tmp;

        cin>>tmp;

        mp[i][T]=tmp;

    }

    for(int i=;i<=n;++i)

    {

        int tmp;

        cin>>tmp;

        mp[S][i]=tmp;

    }

    cin>>m;

    for(int i=;i<=m;++i)

    {

        int a,b;

        cin>>a>>b;

        mp[b][a]=INF;

    }

}

bool bfs()

{

    memset(dep,,sizeof(dep));

    dep[S]=;

    queue<int> q;

    q.push(S);

    for(;q.size();)

    {

        int fr=q.front();

        q.pop();

        for(int i=;i<=T;++i)

        {

            if(!dep[i]&&mp[fr][i])

            {

                dep[i]=dep[fr]+;

                q.push(i);

                if(i==T)return ;

            }

        }

    }

    return ;

}

int dinic(int x,int flow)

{

    if(x==T)return flow;

    else

    {

        int rem=flow;

        for(int i=;i<=T&&rem;++i)

        {

            if(dep[i]==dep[x]+&&mp[x][i])

            {

                int tmp=dinic(i,min(rem,mp[x][i]));

                if(!tmp)dep[i]=;

                rem-=tmp;

                mp[x][i]-=tmp,mp[i][x]+=tmp;

            }

        }

        return flow-rem;

    }

}

bool vst[SZ];

void work()

{

    int res=,ans=;

    for(;bfs();)res+=dinic(S,INF);

    queue<int> q;

    for(int i=;i<=n;++i)

    {

        if(mp[i][T])

        {

            vst[i]=;

            q.push(i);

        }

    }

    for(;q.size();)

    {

        int fr=q.front();

        q.pop();

        for(int i=;i<=n;++i)

        {

            if(mp[i][fr]&&!vst[i])

            {

                vst[i]=;

                q.push(i);

            }

        }

    }

    for(int i=;i<=n;++i)if(vst[i])++ans;

    cout<<res<<" "<<n-ans<<endl;

}

void release()

{

    memset(mp,,sizeof(mp));

    memset(vst,,sizeof(vst));

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    //cout<<(1<<31)<<endl;

    int casenum;

    //cin>>casenum;

    //cout<<casenum<<endl;

    //for(int time=1;time<=casenum;++time)

    for(int time=;cin>>n;++time)

    {

        init();

        work();

        release();

    }

    return ;

}