二分答案,最大流进行判断
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=40005,inf=1000000;
const double esp=0.000000001;
int n,m,S,T;
int a[N],b[N];
struct oppo{
int to,nex;
double s;
}rod[M];
int head[N],tot;
void add(int from,int to,double s)
{
rod[tot].to=to;
rod[tot].nex=head[from];
rod[tot].s=s;
head[from]=tot++;
}
void link(int from,int to,double s)
{
add(from,to,s);
add(to,from,0);
}
int d[N],cur[N];
bool bfs()
{
queue<int> v;
memset(d,-1,sizeof(d));
d[S]=0,cur[S]=head[S];
v.push(S);
while(v.size())
{
int lxl=v.front();v.pop();
for(int i=head[lxl];~i;i=rod[i].nex)
{
int to=rod[i].to;
if(d[to]==-1&&rod[i].s>esp){
d[to]=d[lxl]+1;
cur[to]=head[to];
if(to==T){
return 1;
}
v.push(to);
}
}
}
return 0;
}
double find(int x,double low)
{
if(x==T) return low;
double all=0;
for(int i=cur[x];~i;i=rod[i].nex){
cur[x]=i;
int to=rod[i].to;
if(d[to]==d[x]+1&&rod[i].s>esp){
double t=find(to,min(rod[i].s,low-all));
if(t<esp) d[to]=-1;
rod[i].s-=t;
rod[i^1].s+=t;
all+=t;
}
if(fabs(low-all)<esp) break;
}
return all;
}
double kb;
bool check(double k)
{
for(int i=0;i<2*m;i+=2){//边权重新赋值
rod[i].s=b[(i/2)+1]*k;
rod[i^1].s=0;
}
for(int i=2*m;i<tot;i+=2){//边权清零
rod[i].s+=rod[i^1].s;
rod[i^1].s=0;
}
double ans=0,r;
while(bfs()) while(r=find(S,inf)) ans+=r;
return fabs(kb-ans)<esp;
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m;
S=0,T=n+m+1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
kb+=a[i];
}
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
link(S,i,b[i]);
}
for(int i=1;i<=n;i++) link(i+m,T,a[i]);
for(int i=1;i<=m;i++){
int t;
for(int j=1;j<=n;j++){
scanf("%d",&t);
if(t) link(i,j+m,inf);
}
}
double l=esp,r=10000,mid,ans;
while(fabs(r-l)>esp)
{
mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-esp;
}else
l=mid+esp;
}
printf("%lf",ans);
return 0;
}