51Nod1442 士兵的旅行

题目看这里

一看这种分配式的题目马上联想到网络流

顺手一个SAP板子直接0ms上rank1

拆点建图x,y

1.s->x[i]边权a[i]

2.y[i]->t边权b[i]

3.对于原图每条边p->q,x[p]->y[q]边权∞

4.x[i]->y[i]边权∞

#pragma GCC opitmize("O3")
#pragma G++ opitmize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1010
using namespace std;
struct edge{ int v,c,nt; } G[N<<1];
int n,m,cnt=1,sa,sb,a[N],b[N],h[N],lvl[N],cur[N],gap[N],f[N];
inline void adj(int x,int y,int c){
    G[++cnt]=(edge){y,c,h[x]}; h[x]=cnt;
    G[++cnt]=(edge){x,0,h[y]}; h[y]=cnt;
}
inline int SAP(int s,int t){
    memset(f,-1,sizeof f);
    memcpy(cur,h,sizeof h);
 int u=f[s]=s,ans=0,fw=1<<30; *gap=n;
 for(;lvl[s]<n;){
        begin:
 for(int& i=cur[u],v;i;i=G[i].nt)
 if(G[i].c && lvl[v=G[i].v]+1==lvl[u]){
                fw=min(fw,G[i].c); f[v]=u; u=v;
 if(v==t){
                    ans+=fw;
 for(u=f[v];v!=s;v=u,u=f[u]){
                        G[cur[u]].c-=fw;
                        G[cur[u]^1].c+=fw;
 }
                    fw=1<<30;
 }
 goto begin;
 }
 int ml=n;
 for(int v,i=h[u];i;i=G[i].nt)
 if(G[i].c && ml>lvl[v=G[i].v]){
                cur[u]=i; ml=lvl[v];
 }
 if(--gap[lvl[u]]==0) break;
        gap[lvl[u]=ml+1]++; u=f[u];
 }
 return ans;
}
int main(){
    scanf("%d%d",&n,&m);
 for(int i=1;i<=n;++i) scanf("%d",a+i),sa+=a[i];
 for(int i=1;i<=n;++i) scanf("%d",b+i),sb+=b[i];
 if(sa!=sb) return 0&puts("NO");
 for(int x,y,i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        adj(x,y+n,1000);
        adj(y,x+n,1000);
 }
    m=n; n<<=1; ++n;
 for(int i=1;i<=m;++i){
        adj(i,i+m,1000);
        adj(n,i,a[i]);
        adj(i+m,n+1,b[i]);
 }
 ++n;
 if(SAP(n-1,n)==sa) puts("YES"); else puts("NO");
}