非官方题解 | A85334.研发计划

这道题题目里很详细了，我就不多赘述了。
这是我的马蜂：
能过，还好，写了5次代码，只过了2次，坑，但总体很水

Code:

namespace CuSn{
    #define N 1009
    #define M 500009
    #define rep(i,x,y) for(int i=(x);i<=(y);++i)
    typedef long long ll;
    const int inf=0x3f3f3f3f;
    int nV,n,m,hd[N],tot,now[N],d[N],s,t,p,q;
    ll maxf;
    struct edge{int t,w,nxt;}es[M<<1];
    void adde(int u,int v,int w){
        es[++tot]=(edge){v,w,hd[u]},hd[u]=tot;
        es[++tot]=(edge){u,0,hd[v]},hd[v]=tot;
    }
    bool bfs(){
        queue<int>q;
        fill(d+1,d+nV+1,0);
        copy(hd+1,hd+nV+1,now+1);
        q.push(s);
        d[s]=1;
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=hd[u],v;i;i=es[i].nxt)
                if(es[i].w&&!d[v=es[i].t]){
                    d[v]=d[u]+1;
                    q.push(v);
                }
        }
        return d[t];
    }
    int dinic(int u,int f){
        if(u==t)return f;
        int r=f;
        for(int i=now[u],v;i&&r;i=es[i].nxt)
            if(es[now[u]=i].w&&d[v=es[i].t]==d[u]+1){
                int k=dinic(v,min(r,es[i].w));
                es[i].w-=k,es[i^1].w+=k,r-=k;
            }
        return f-r;
    }
    void solve(){
        cin>>n>>m>>p>>q;
        tot=1;
        nV=t=2*n+m+2;
        s=t-1;
        ll ans=0;
        for(int i=1;i<=n;++i){
            int f;cin>>f;
            adde(i,i+n,f);
        }
        for(int i=1;i<=n;++i){
            int h;cin>>h;
            adde(s,i,h);
        }
        for(int i=1;i<=m;++i){
            int g;cin>>g;
            ans+=g;
            adde(2*n+i,t,g);
        }
        for(int i=1;i<=p;++i){
            int u,v;cin>>u>>v;
            adde(u+n,v+2*n,inf);
        }
        for(int i=1;i<=q;++i){
            int a,b;cin>>a>>b;
            adde(a+n,b,inf);
        }
        while(bfs())ans-=dinic(s,inf);
        cout<<ans<<'\n';
    }
}