刚学OI 6小时萌新求助

#include<bits/stdc++.h>
#define ll long long 
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define INF 1234567890
#define mid ((l+r)>>1)
#define N 105
using namespace std;

int n,m,S=0,T=1000,dep[N];
ll a[N],b[N],sum=0;
bool can[N][N];
//第i个武器能否攻击第j个机器人

int cnt=1,head[N<<2];
struct Edge
{
	int to,next;
	ll dis;
}e[N<<2];

inline void add_edge(int from,int to,ll dis)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].dis=dis;
	head[from]=cnt;
}

bool bfs()
{
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(S);dep[S]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(!dep[v]&&e[i].dis)
			{
				dep[v]=dep[u]+1;
				q.push(v);
				if(v==T) return 1;
			}
		}
	}
	return 0;
}

ll dfs(int u,ll rest)
{
	if(u==T) return rest;
	ll used=0;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(dep[v]==dep[u]+1&&e[i].dis)
		{
			ll k=dfs(v,min(e[i].dis,rest-used));
			if(!k) {dep[v]=0;continue;}
			used+=k;
			e[i].dis-=k;
			e[i^1].dis+=k;
		}
	}
	return used;
}

ll dinic()
{
	ll res=0;
	while(bfs()) res+=dfs(S,INF);
	return res;
}

bool check(ll t)
{
	memset(head,0,sizeof(head));cnt=1;
	fo(i,1,n) add_edge(S,i,b[i]*t),add_edge(i,S,0);//S向激光连线
	fo(i,1,n) add_edge(m+i,T,a[i]),add_edge(T,m+i,0);//机器人向T连线
	fo(i,1,m) fo(j,1,n) if(can[i][j]) add_edge(i,m+j,INF),add_edge(m+j,i,0);//激光连机器人
	return (dinic()==sum);
}

template<class T>inline void read(T &res)
{
	T flag=1;char c;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';res*=flag;
}

int main()
{
	read(n);read(m);
	fo(i,1,n) read(a[i]),a[i]*=10000,sum+=a[i];
	fo(i,1,m) read(b[i]),b[i]*=10000;
	fo(i,1,m) fo(j,1,n) read(can[i][j]);
	ll l=0,r=1000000000;
	while(l<r)
	{
		if(check(mid)) r=mid;//流量等于所有生命值
		else l=mid+1;
	}
	printf("%.6lf\n",(double)l/10000.0);
	return 0;
}