bzoj 3993: [Sdoi2015]星际战争

Description

3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

Input

第一行，两个整数，N、M。

第二行，N个整数，A1、A2…AN。

第三行，M个整数，B1、B2…BM。

接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。

Output

一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。

Sample Input

2 2
3 10
4 6
0 1
1 1

Sample Output

1.300000

HINT

【样例说明1】

战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；

接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。

对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

Source

Round 1 感谢yts1999上传

二分时间，然后建边两排点跑网络流。源左边一排。流量为攻击输出。右边一排连汇。流量为装甲值。中间互连。流量无限

【记得弄eps，小心别被卡精度】

#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct line
{
     int s,t;
     double f;
     int next;
}a[100001];
int head[1001];
int edge;
double eps=10e-5;
inline void add(int s,int t,double f)
{
	 a[edge].next=head[s];
     head[s]=edge;
     a[edge].s=s;
     a[edge].t=t;
     a[edge].f=f;
}
double aa[1001],bb[1001];
int dep[1001],q[100001];
int map[1001][1001];
int p;
inline bool bfs(int d)
{
	 memset(dep,-1,sizeof(dep));
     int l=1,r=0;
     int i;
     r++;
     q[r]=d;
     dep[d]=0;
     while(l<=r)
     {
     	  d=q[l];
          for(i=head[d];i!=0;i=a[i].next)
          {
               int t=a[i].t;
               if(dep[t]==-1&&a[i].f>0)
               {
                    dep[t]=dep[d]+1;
                    r++;
                    q[r]=t;
               }
          }
		  l++;
     }
     if(dep[p]!=-1)
          return true;
     return false;
}
inline double dfs(int d,double s)
{
     if(d==p)
          return s;
     double ts=s;
     int i;
     for(i=head[d];i!=0;i=a[i].next)
     {
          int t=a[i].t;
          if(dep[t]==dep[d]+1&&a[i].f>0)
          {
               double tx=dfs(t,min(a[i].f,s));
               s-=tx;
               a[i].f-=tx;
               if(i%2==0)
                    a[i-1].f+=tx;
               else
                    a[i+1].f+=tx;
          }
     }
     return ts-s;
}
inline double dinic()
{
     double s=0;
     while(bfs(0))
          s+=dfs(0,2100000000);
     return s;
}
int main()
{
     int n,m;
     scanf("%d%d",&n,&m);
     int i,j;
     double sum=0;
     for(i=1;i<=n;i++)
     {
          scanf("%lf",&aa[i]);
          sum+=aa[i];
     }
     for(i=1;i<=m;i++)
          scanf("%lf",&bb[i]);
	 for(i=1;i<=m;i++)
	      for(j=1;j<=n;j++)
	           scanf("%d",&map[i][j]);
	 double l=0,r=5000000;
	 p=n+m+1;
	 while(l<=r)
	 {
	 	  memset(a,0,sizeof(a));
	 	  memset(head,0,sizeof(head));
	 	  edge=0;
	      double mid=(l+r)/(double)2;
	      double flow;
	      for(i=1;i<=m;i++)
	      {
	           flow=mid*bb[i];
	           edge++;
	           add(0,i,flow);
	           edge++;
	           add(i,0,0);
	      }
	      for(i=1;i<=m;i++)
	      {
	           for(j=1;j<=n;j++)
	           {
	                if(map[i][j]==1)
	                {
	                     edge++;
	                     add(i,j+m,2100000000);
	                     edge++;
	                     add(j+m,i,0);
	                }
	           }
	      }
	      for(i=1;i<=n;i++)
	      {
	           edge++;
	           add(i+m,p,aa[i]);
	           edge++;
	           add(p,i+m,0);
	      }
	      double tt=dinic();
	      if(tt+eps>=sum)
	           r=mid-0.0001;
	      else
	           l=mid+0.0001;
	 }
	 printf("%lf\n",l);
     return 0;
}