1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i) template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO; template <class T=int> T rd(){ T s=0; int f=0; while(!isdigit(IO=getchar())) f|=IO=='-'; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; }
enum{N=10101,INF=1<<30};
int n,m,W; int c[N],t[N],X[N],Y[N]; struct Edge{ int to,nxt,w,c; } e[N]; int head[N],ecnt=1; int V,S,T; void AddEdge(int u,int v,int w,int c){ e[++ecnt]=(Edge){v,head[u],w,c},head[u]=ecnt; } void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }
int pre[N],dis[N],inq[N]; int SPFA(int lim){ rep(i,1,V) dis[i]=-INF; static queue <int> que; dis[S]=-lim,que.push(S); while(!que.empty()) { int u=que.front(); que.pop(),inq[u]=0; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if(!e[i].w || dis[v]>=dis[u]+e[i].c) continue; dis[v]=dis[u]+e[i].c,pre[v]=i; if(!inq[v]) que.push(v),inq[v]=1; } } return dis[T]>0; }
int Check(int lim){ S=++V,T=++V; rep(i,1,n) { Link(S,++V,INF,0); Link(V,V+1,c[i],t[i]); Link(V,V+1,INF,0); Link(++V,T,INF,0); } rep(i,1,m) Link(X[i]*2+2,Y[i]*2+1,INF,0); int ans=0; while(SPFA(lim)){ int w=INF; for(int i=T;i!=S;i=e[pre[i]^1].to) cmin(w,e[pre[i]].w); for(int i=T;i!=S;i=e[pre[i]^1].to) e[pre[i]].w-=w,e[pre[i]^1].w+=w; ans+=dis[T]*w; } rep(i,1,V) head[i]=0; ecnt=1,V=0; return ans<=W; }
int main(){ freopen("soft.in","r",stdin),freopen("soft.out","w",stdout); n=rd(),m=rd(),W=rd(); int l=0,r=0,res=-1; rep(i,1,n) r+=t[i]=rd(); rep(i,1,n) c[i]=rd(); rep(i,1,m) X[i]=rd(),Y[i]=rd(); for(int mid;l<=r;) Check(mid=(l+r)>>1)?r=mid-1,res=mid:l=mid+1; printf("%d\n",res); }
|