#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-12;
typedef long long lon;
const lon SZ=210,SSZ=210,APB=10000,one=1,INF=0x7FFFFFFF,mod=1000000007;
int n,m,S=207,T=208,mp[SZ][SZ];
int dep[SZ];

void init()
{
    for(int i=1;i<=n;++i)
    {
        int tmp;
        cin>>tmp;
        mp[i][T]=tmp;
    }
    for(int i=1;i<=n;++i)
    {
        int tmp;
        cin>>tmp;
        mp[S][i]=tmp;
    }
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        mp[b][a]=INF;
    }
}

bool bfs()
{
    memset(dep,0,sizeof(dep));
    dep[S]=1;
    queue<int> q;
    q.push(S);
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        for(int i=1;i<=T;++i)
        {
            if(!dep[i]&&mp[fr][i])
            {
                dep[i]=dep[fr]+1;
                q.push(i);
                if(i==T)return 1;
            }
        }
    }
    return 0;
}

int dinic(int x,int flow)
{
    if(x==T)return flow;
    else
    {
        int rem=flow;
        for(int i=1;i<=T&&rem;++i)
        {
            if(dep[i]==dep[x]+1&&mp[x][i])
            {
                int tmp=dinic(i,min(rem,mp[x][i]));
                if(!tmp)dep[i]=0;
                rem-=tmp;
                mp[x][i]-=tmp,mp[i][x]+=tmp;
            }
        }
        return flow-rem;
    }
}

bool vst[SZ];

void work()
{
    int res=0,ans=0;
    for(;bfs();)res+=dinic(S,INF);
    queue<int> q;
    for(int i=1;i<=n;++i)
    {
        if(mp[i][T])
        {
            vst[i]=1;
            q.push(i);
        }
    }
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        for(int i=1;i<=n;++i)
        {
            if(mp[i][fr]&&!vst[i])
            {
                vst[i]=1;
                q.push(i);
            }
        }
    }
    for(int i=1;i<=n;++i)if(vst[i])++ans;
    cout<<res<<" "<<n-ans<<endl;
}

void release()
{
    memset(mp,0,sizeof(mp));
    memset(vst,0,sizeof(vst));
}

int main()
{
    std::ios::sync_with_stdio(0);
    //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=1;cin>>n;++time)
    {
        init();
        work();
        release();
    }
    return 0;
}

 

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

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄