Bzoj3993: [SDOI2015] interstellar warfare (two points + maximum flow)

Title Description

3333In the year of the galaxy, the X corps and the Y regiment are fighting fiercely.

At one stage of the battle, Legion Y dispatched a total of N giant robots to attack Legion X positions, of which the armor value of the first giant robot was Ai. When the armor value of a giant robot is reduced to zero or less, the giant robot is destroyed.

XThe Legion has M laser weapons, the second of which can reduce the armor value of a giant robot Bi per second. The attack of laser weapons is continuous.

This laser weapon is very strange. A laser weapon can only attack certain enemies. Legion Y saw their giant robots destroyed one by one by Legion X, and they urgently needed more instructions.

To do this, Legion Y needs to know how long it will take Legion X at least to destroy all of Legion Y’s giant robots. But they will not calculate this problem, so they turn to you for help.

Input output format

Input format:

The first line, two integers, N, M. Second rows, N integers, A1, A2… AN. Third rows, M integers, B1, B2… BM. The next M line is N integers per row, and these integers are 0 or 1. The j integer in line I of this part is 0, indicating the first I excitation.Light weapons can not attack the jth giant robot, 1 means the 1st laser weapon can attack the jth giant robot.

Output format:

One line, a real number, represents the minimum time that Legion X needs to destroy all of Legion Y’s giant robots. The absolute error of the output and standard answer is not more than 10-3, which is considered correct.

Examples of input and output

2 2
3 10
4 6
0 1
1 1

1.300000

Explain

【Example 1

In the first 0.5 seconds after the battle began, Laser Weapon 1 attacked Giant Robot 2 and Laser Weapon 2 attacked Giant Robot 1. The 1 giant robot was completely destroyed, and the 2 giant robot still had 8 armor value.

In the next 0.8 seconds, laser weapons 1 and 2 attack 2 giant robots simultaneously. The 2 giant robot was completely destroyed.

For all data, 1< =N, M< =50, 1< =Ai&lt = =10^5105，1<=Bi<=1000，Input data ensure that the X Legion will destroy all giant robots of the Y regiment.

An explanation

　　First look at the past: is it a naked cost flow?

　　The second eye: the answer is a real number.

　　Then GG, run to see the solution.

　　My original idea was to run a minimal cost stream (and then find myself sb… Because the cost of different lasers will be counted together.

　　However, the number of days may be real.

　　Then we can consider the two point answer, enumerate for a few days, and then build the following as follows

　　For each laser weapon, we’re flanking him from the source with a capacity of * days of attack.

　　For each robot, we connect it to the confluence side, with a volume of blood (representing that he can withstand so many attacks)

　　Then laser can connect the robot that can be attacked.

　　Then run a maximum flow to see if the flow is equal to the total blood volume of the robot.

　　However, because they are real numbers with an accuracy of $1e-3, we can multiply all the numbers by $10,000 to eliminate the effect of precision.

　　Then you need to open a lot of $long\ long$, so…  #define int long long Understand?

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 #define int long long
 7 #define inf 1e15
 8 using namespace std;
 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
10 char buf[1<<21],*p1=buf,*p2=buf;
11 inline int read(){
12     #define num ch-'0'
13     char ch;bool flag=0;int res;
14     while(!isdigit(ch=getc()))
15     (ch=='-')&&(flag=true);
16     for(res=num;isdigit(ch=getc());res=res*10+num);
17     (flag)&&(res=-res);
18     #undef num
19     return res;
20 }
21 const int N=205,M=50005;
22 int head[N],Next[M],ver[M],edge[M],tot;
23 inline void init(){memset(head,0,sizeof(head)),tot=1;}
24 inline void add(int u,int v,int e){
25     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
26     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=0;
27 }
28 int dep[N],cur[N],n,m,s,t;
29 queue<int> q;
30 bool bfs(){
31     memset(dep,-1,sizeof(dep));
32     while(!q.empty()) q.pop();
33     for(int i=s;i<=t;++i) cur[i]=head[i];
34     q.push(s),dep[s]=0;
35     while(!q.empty()){
36         int u=q.front();q.pop();
37         for(int i=head[u];i;i=Next[i]){
38             int v=ver[i];
39             if(dep[v]<0&&edge[i]){
40                 dep[v]=dep[u]+1,q.push(v);
41                 if(v==t) return true;
42             }
43         }
44     }
45     return false;
46 }
47 int dfs(int u,int limit){
48     if(u==t||!limit) return limit;
49     int flow=0,f;
50     for(int i=cur[u];i;i=Next[i]){
51         int v=ver[i];cur[u]=i;
52         if(dep[v]==dep[u]+1&&(f=dfs(v,min(limit,edge[i])))){
53             flow+=f,limit-=f;
54             edge[i]-=f,edge[i^1]+=f;
55             if(!limit) break;
56         }
57     }
58     if(!flow) dep[u]=-1;
59     return flow;
60 }
61 int dinic(){
62     int flow=0;
63     while(bfs()) flow+=dfs(s,inf);
64     return flow;
65 }
66 bool x[N][N];int hp[N],atk[N],sum;
67 void build(int tim){
68     init();
69     for(int i=1;i<=n;++i) add(s,i,tim*atk[i]);
70     for(int i=1;i<=m;++i) add(i+n,t,hp[i]);
71     for(int i=1;i<=n;++i)
72     for(int j=1;j<=m;++j)
73     if(x[i][j]) add(i,j+n,inf);
74 }
75 signed main(){
76     //freopen("testdata.in","r",stdin);
77     m=read(),n=read(),s=0,t=n+m+1;
78     for(int i=1;i<=m;++i) hp[i]=read()*10000ll,sum+=hp[i];
79     for(int i=1;i<=n;++i) atk[i]=read();
80     for(int i=1;i<=n;++i)
81     for(int j=1;j<=m;++j)
82     x[i][j]=read();
83     int l=0,r=10000000000ll,ans=0;
84     while(l<=r){
85         int mid=l+r>>1;
86         build(mid);
87         if(dinic()>=sum) ans=mid,r=mid-1;
88         else l=mid+1;
89     }
90     printf("%.4lf\n",ans/10000.0);
91     return 0;
92 }