题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3993
二分最大流就可以了。
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<set> #include<cmath> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 3005 #define inf 1e9 #define mm 1000000007 #define eps 1e-7 typedef long long ll; using namespace std; struct data{int obj,pre;double c; }e[maxn*2]; int tot,n,m,t,head[maxn],uu[maxn],cur[maxn],mp[60][60]; double sum,a[maxn],b[maxn]; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y,double z){ e[++tot].obj=y; e[tot].pre=head[x]; e[tot].c=z; head[x]=tot; e[++tot].obj=x; e[tot].pre=head[y]; e[tot].c=0; head[y]=tot; } bool bfs(){ clr(uu,-1); uu[0]=0; queue<int> q; q.push(0); while (!q.empty()){ int u=q.front(); q.pop(); for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (e[j].c>eps&&uu[v]==-1) uu[v]=uu[u]+1,q.push(v); } } return uu[t]!=-1; } double dfs(int x,double mx){ double used=0; if (x==t) return mx; for (int j=head[x];j;j=e[j].pre){ int v=e[j].obj; if (uu[v]==uu[x]+1&&fabs(e[j].c)>eps){ double w=dfs(v,min(e[j].c,mx-used)); used+=w; e[j].c-=w; e[j^1].c+=w; if (fabs(e[j].c)>eps) cur[x]=j; if (fabs(mx-used)<=eps) return used; } } if (used<=eps) uu[x]=-1; return used; } double dinic(){ double ans=0; while (bfs()){ rep(i,0,t) cur[i]=head[i]; ans+=dfs(0,inf); //printf("%.3lf ",ans); } return ans; } bool jud(double mid){ clr(head,0); tot=1; rep(i,1,m) insert(0,i,b[i]*mid); rep(i,1,n) insert(i+m,t,a[i]); rep(i,1,m) rep(j,1,n) if (mp[i][j]) insert(i,j+m,inf); if (dinic()>=(sum-eps)) return 1; return 0; } int main(){ // freopen("in.txt","r",stdin); n=read(); m=read(); rep(i,1,n) scanf("%lf",&a[i]),sum+=a[i]; rep(i,1,m) scanf("%lf",&b[i]); rep(i,1,m) rep(j,1,n) mp[i][j]=read(); t=n+m+1; double l=0,r=inf; while (fabs(r-l)>eps){ double mid=(l+r)/2; if (jud(mid)) r=mid; else l=mid; } printf("%.6lf ",l); return 0; }