题目：洛谷P3324 [SDOI2015]星际战争
思路：
类似《导弹防御塔》，因为题目保证有解，花费时间小于最终答案时一定无法消灭所有敌人，只要花费时间大于等于最终答案都可以消灭所有敌人，答案满足单调性，考虑二分答案。
二分答案后，转化为判定性问题。当总时间固定，每件武器的总伤害量就确定了。
于是可以按网络流建模：把武器和敌人分成两部分，从源点s向武器连边，容量为该武器可以输出的总伤害量（当前二分到的时间time*该武器的dps）；每件武器向可以它攻击到的敌人连边，容量为inf；每个敌人向汇点t连边，容量为该敌人的生命上限。最后只需判断最大流是否等于敌人总生命值。
因为时间是小数，代码中采用double存储。最后要求三位小数，也可以把所有数据都乘10000变成整数以提高精度。
注意我的代码中n、m、a、b与题目中相反。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5,inf=0x3f3f3f3f;
const double eps=1e-4;
double sum,a[N],b[N],val[N];
int n,m,s,t,tot,mp[505][505],d[N];
int Top=1,ver[N],nxt[N],head[N];
inline void add(int u,int v,double w){
ver[++Top]=v;val[Top]=w;nxt[Top]=head[u];head[u]=Top;
ver[++Top]=u;val[Top]=0;nxt[Top]=head[v];head[v]=Top;
}
bool bfs(){
for(int i=1;i<=tot;++i) d[i]=0;
queue<int> q;
q.push(s);
d[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(val[i]>eps&&!d[v]){
d[v]=d[u]+1;
if(v==t) return true;
q.push(v);
}
}
}
return false;
}
double dfs(int u,double flow){
if(u==t) return flow;
double left=flow;
for(int i=head[u];i&&left;i=nxt[i]){
int v=ver[i];
if(val[i]>eps&&d[v]==d[u]+1){
double res=dfs(v,min(left,val[i]));
if(!res) d[v]=0;
val[i]-=res;
val[i^1]+=res;
left-=res;
}
}
return flow-left;
}
bool check(double tim){
memset(head,0,sizeof(head));
memset(ver,0,sizeof(ver));
memset(nxt,0,sizeof(nxt));
memset(val,0,sizeof(val));
Top=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(mp[i][j]) add(i,n+j,inf);
}
}
for(int i=1;i<=n;++i) add(s,i,tim*a[i]);
for(int i=1;i<=m;++i) add(n+i,t,b[i]);
double res=0;
while(bfs()) {
res+=dfs(s,inf);
}
return fabs(res-sum)<eps;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i) scanf("%lf",&b[i]);
for(int i=1;i<=n;++i) scanf("%lf",&a[i]);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&mp[i][j]);
}
}
tot=n+m;
s=++tot;
t=++tot;
for(int i=1;i<=m;++i) sum+=b[i];
double l=0,r=2e5;
while(r-l>eps){
double mid=(l+r)*0.5;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.3lf",l);
return 0;
}