题目描述
3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。
输入
第一行，两个整数，N、M。
第二行，N个整数，A1、A2…AN。
第三行，M个整数，B1、B2…BM。
接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。
输出
一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。
样例输入
2 2
3 10
4 6
0 1
1 1
样例输出
1.300000
题解
二分+最大流，apio讲过的题。
设激光武器为xi，机器人为yi。
二分时间mid，S->xi，容量为bi*mid（需要保留小数）；xi->能够攻击的yi，容量为inf；yi->T，容量为ai。
判断是否满流，并更新答案。
由于二分的时间是小数，所以最好是限制迭代次数，达到次数后跳出循环即可。
#include <cstdio>
#include <cstring>
#include <queue>
#define N 110
#define M 100000
#define inf 1000000000
using namespace std;
queue<int> q;
double a[N] , b[N] , val[M];
int n , m , p[N][N] , head[N] , to[M] , next[M] , cnt = 1 , s , t , dis[N];
void add(int x , int y , double z)
{
to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;
to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;
}
bool bfs()
{
int x , i;
memset(dis , 0 , sizeof(dis));
while(!q.empty()) q.pop();
dis[s] = 1 , q.push(s);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
if(val[i] > 0 && !dis[to[i]])
{
dis[to[i]] = dis[x] + 1;
if(to[i] == t) return 1;
q.push(to[i]);
}
}
}
return 0;
}
double dinic(int x , double low)
{
if(x == t) return low;
double temp = low , k;
int i;
for(i = head[x] ; i ; i = next[i])
{
if(val[i] > 0 && dis[to[i]] == dis[x] + 1)
{
k = dinic(to[i] , min(temp , val[i]));
if(k <= 0) dis[to[i]] = 0;
val[i] -= k , val[i ^ 1] += k;
if((temp -= k) <= 0) break;
}
}
return low - temp;
}
bool judge(double mid)
{
int i , j;
double sum = 0;
memset(head , 0 , sizeof(head)) , cnt = 1;
for(i = 1 ; i <= m ; i ++ ) add(s , i , b[i] * mid);
for(i = 1 ; i <= n ; i ++ ) add(i + m , t , a[i]) , sum += a[i];
for(i = 1 ; i <= m ; i ++ )
for(j = 1 ; j <= n ; j ++ )
if(p[i][j])
add(i , j + m , inf);
while(bfs()) sum -= dinic(s , inf);
return sum <= 0;
}
int main()
{
int i , j , tot = 100;
double l = 0 , r = 1000000 , mid;
scanf("%d%d" , &n , &m) , s = 0 , t = n + m + 1;
for(i = 1 ; i <= n ; i ++ ) scanf("%lf" , &a[i]);
for(i = 1 ; i <= m ; i ++ ) scanf("%lf" , &b[i]);
for(i = 1 ; i <= m ; i ++ )
for(j = 1 ; j <= n ; j ++ )
scanf("%d" , &p[i][j]);
while(tot -- )
{
mid = (l + r) / 2;
if(judge(mid)) r = mid;
else l = mid;
}
printf("%.6lf
" , r);
return 0;
}