Lvat_s Blog

二分时间，跑实数网络流就可以了

貌似速度还很快- -

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;

const int INF=2100000000;
const double eps=1e-6;

int n,m,level[5005],h[5005],cur[5005],S,T,en,Mt[55][55];
double A[55],B[55],Sum;
queue<int> Q;

struct Edge{
int b,back,next;
double f;
}e[100005];

double Abs(double x){return x>0?x:-x;}

void AddEdge(int sa,int sb,double sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
        if(e[i].f<eps || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
	}
}
return level[T];
}

double DFS(int u,double flow){
if(u==T)return flow;
double f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    double fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))>eps){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f<eps)return flow;
    }
}
return flow-f;
}

double Dinic(){
double ans=0;
while(BFS()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=DFS(S,(double)INF);}
return ans;
}

bool Test(double Ts){
memset(h,0,sizeof(h));
en=0;
S=n+m+1;
T=n+m+2;
for(int i=1;i<=m;i++)AddEdge(S,i,Ts*B[i]);
for(int i=1;i<=n;i++)AddEdge(i+m,T,A[i]);
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		if(Mt[i][j])AddEdge(i,j+m,INF);
	}
}
return Abs(Dinic()-Sum)<eps;
}

double Div(){
double l=0,r=100000000,ans;
while(r-l>eps){
	double mid=l/2+r/2;
	if(Test(mid)){ans=mid;r=mid;}
	else l=mid;
}
return ans;
}

int main(){
freopen("3993.in","r",stdin);
freopen("3993.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%lf",&A[i]);Sum+=A[i];}
for(int i=1;i<=m;i++){scanf("%lf",&B[i]);}
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		scanf("%d",&Mt[i][j]);
	}
}
printf("%lf\n",Div());
return 0;
}