题目
分析
二分答案，然后建图判断可行性
代码
#include <cstdio>
#include <cctype>
#include <queue>
#define rr register
using namespace std;
typedef long long lll;
const int N=111; lll sum,ans;
struct node{int y; lll w; int next;}e[5300];
int dis[N],as[N],k=1,n,m,a[N],b[N],Tt,Ss;
inline signed iut(){
rr int ans=0,f=1; rr char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans*f;
}
inline void add(int x,int y,lll w){
e[++k]=(node){y,w,as[x]}; as[x]=k;
e[++k]=(node){x,0,as[y]}; as[y]=k;
}
inline lll min(lll a,lll b){return a<b?a:b;}
inline bool bfs(int Ss){
for (rr int i=1;i<=Tt;++i) dis[i]=0;
rr queue<int>q; q.push(Ss); dis[Ss]=1;
while (q.size()){
rr int x=q.front(); q.pop();
for (rr int i=as[x];i;i=e[i].next)
if (e[i].w>0&&!dis[e[i].y]){
dis[e[i].y]=dis[x]+1;
if (e[i].y==Tt) return 1;
q.push(e[i].y);
}
}
return 0;
}
inline lll dfs(int x,lll now){
if (x==Tt||!now) return now;
rr lll rest=0,f;
for (rr int i=as[x];i;i=e[i].next)
if (e[i].w>0&&dis[e[i].y]==dis[x]+1){
rest+=(f=dfs(e[i].y,min(now-rest,e[i].w)));
e[i].w-=f; e[i^1].w+=f;
if (now==rest) return rest;
}
if (!rest) dis[x]=0;
return rest;
}
inline bool check(lll mid){
for (rr int i=2;i<=k;i+=2){
if (i<2*n+2) e[i].w=mid*b[i>>1],e[i^1].w=0;
else if (i<2*(n+m+1)) e[i].w=a[(i>>1)-n],e[i^1].w=0;
else e[i].w=1e15,e[i^1].w=0;
}
for (ans=0;bfs(Ss);) ans+=dfs(Ss,1e15);
return ans>=sum;
}
signed main(){
m=iut(),n=iut(),Ss=n+m+1,Tt=Ss+1,k=1;
for (rr int i=1;i<=m;++i) a[i]=iut()*10000,sum+=a[i];
for (rr int i=1;i<=n;++i) b[i]=iut();
for (rr int i=1;i<=n;++i) add(Ss,i,0);
for (rr int i=1;i<=m;++i) add(i+n,Tt,0);
for (rr int i=1;i<=n;++i)
for (rr int j=1;j<=m;++j){
rr int x=iut();
if (x) add(i,j+n,0);
}
rr lll l=0,r=50000000000ll;
while (l<r){
rr lll mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
return !printf("%lf",l/10000.0);
}