bzoj 3993 星际战争

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

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军团的所有巨型机器人

　　二分时间，然后建图，激光武器和源点相连，容量为这个激光武器在这个时间内能够造成的伤害，机器人和汇点连边，容量为机器人的装甲值，激光武器和它能够攻击的目标连一条边，容量为无限大。

Code

  1 /**
  2  * bzoj
  3  * Problem#3993
  4  * Accepted
  5  * Time:48ms
  6  * Memory:1688k
  7  */
  8 #include <iostream>
  9 #include <cstdio>
 10 #include <ctime>
 11 #include <cmath>
 12 #include <cctype>
 13 #include <cstring>
 14 #include <cstdlib>
 15 #include <fstream>
 16 #include <sstream>
 17 #include <algorithm>
 18 #include <map>
 19 #include <set>
 20 #include <stack>
 21 #include <queue>
 22 #include <vector>
 23 #include <stack>
 24 #ifndef WIN32
 25 #define Auto "%lld"
 26 #else
 27 #define Auto "%I64d"
 28 #endif
 29 using namespace std;
 30 typedef bool boolean;
 31 const signed int inf = (signed)((1u << 31) - 1);
 32 const double eps = 1e-6;
 33 #define smin(a, b) a = min(a, b)
 34 #define smax(a, b) a = max(a, b)
 35 #define max3(a, b, c) max(a, max(b, c))
 36 #define min3(a, b, c) min(a, min(b, c))
 37 template<typename T>
 38 inline boolean readInteger(T& u){
 39     char x;
 40     int aFlag = 1;
 41     while(!isdigit((x = getchar())) && x != '-' && x != -1);
 42     if(x == -1) {
 43         ungetc(x, stdin);
 44         return false;
 45     }
 46     if(x == '-'){
 47         x = getchar();
 48         aFlag = -1;
 49     }
 50     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
 51     ungetc(x, stdin);
 52     u *= aFlag;
 53     return true;
 54 }
 55 
 56 typedef class Edge {
 57     public:
 58         int end;
 59         int next;
 60         double flow;
 61         double cap;
 62         Edge(int end = 0, int next = -1, double flow = 0, double cap = 0):end(end), next(next), flow(flow), cap(cap) {    }
 63 }Edge;
 64 
 65 typedef class MapManager {
 66     public:
 67         int ce;
 68         vector<Edge> edge;
 69         int* h;
 70         
 71         MapManager():ce(0), h(NULL) {        }
 72         MapManager(int nodes):ce(0) {
 73             h = new int[(const int)(nodes + 1)];
 74             memset(h, -1, sizeof(int) * (nodes + 1));
 75         }
 76         
 77         inline void addEdge(int from, int end, double flow, double cap) {
 78             edge.push_back(Edge(end, h[from], flow, cap));
 79             h[from] = ce++;
 80         }
 81         
 82         inline void addDoubleEdge(int from, int end, double cap) {
 83             if(cap == 0)    return;
 84             addEdge(from, end, 0, cap);
 85             addEdge(end, from, cap, cap);
 86         }
 87         
 88         Edge& operator [] (int pos) {
 89             return edge[pos];
 90         }
 91         
 92         inline void clear() {
 93             delete[] h;
 94             edge.clear();
 95         }
 96 }MapManager;
 97 #define m_begin(g, i) (g).h[(i)]
 98 #define m_endpos -1
 99 
100 inline boolean dcmp(double a, double b) {
101     return fabs(a - b) < eps;
102 }
103 
104 template<typename T>class Matrix{
105     public:
106         T *p;
107         int lines;
108         int rows;
109         Matrix():p(NULL){    }
110         Matrix(int rows, int lines):lines(lines), rows(rows){
111             p = new T[(lines * rows)];
112         }
113         T* operator [](int pos){
114             return (p + pos * lines);
115         }
116 };
117 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows)
118 
119 int n, m;
120 int *A, *B;
121 int sA = 0;
122 int s, t;
123 Matrix<boolean> atable;
124 
125 inline void init() {
126     readInteger(n);
127     readInteger(m);
128     A = new int[(const int)(n + 1)];
129     B = new int[(const int)(m + 1)];
130     atable = Matrix<boolean>(m + 1, n + 1);
131     for(int i = 1; i <= n; i++)
132         readInteger(A[i]), sA += A[i];
133     for(int i = 1; i <= m; i++)
134         readInteger(B[i]);
135     for(int i = 1; i <= m; i++)
136         for(int j = 1; j <= n; j++)
137             readInteger(atable[i][j]);
138     s = 0, t = n + m + 1;
139 }
140 
141 MapManager g;
142 inline void mkmap(double mid) {
143     g = MapManager(n + m + 1);
144     for(int i = 1; i <= m; i++)
145         g.addDoubleEdge(s, i, B[i] * mid); 
146     for(int i = 1; i <= n; i++)
147         g.addDoubleEdge(i + m, t, A[i]); 
148     for(int i = 1; i <= m; i++)
149         for(int j = 1; j <= n; j++)
150             if(atable[i][j])
151                 g.addDoubleEdge(i, j + m, inf); 
152 }
153 
154 int* dis;
155 boolean* vis;
156 queue<int> que;
157 inline boolean bfs() {
158     memset(vis, false, sizeof(boolean) * (t + 1));
159     que.push(s);
160     vis[s] = true;
161     dis[s] = 0;
162     while(!que.empty()) {
163         int e = que.front();
164         que.pop();
165         for(int i = m_begin(g, e); i != m_endpos; i = g[i].next) {
166             if(dcmp(g[i].cap, g[i].flow))    continue;
167             int eu = g[i].end;
168             if(vis[eu])    continue;
169             vis[eu] = true;
170             dis[eu] = dis[e] + 1;
171             que.push(eu);
172         }
173     }
174     return vis[t];
175 }
176 
177 int *cur;
178 inline double blockedflow(int node, double minf) {
179     if((node == t) || (minf < eps))    return minf;
180     double f, flow = 0;
181     for(int& i = cur[node]; i != m_endpos; i = g[i].next) {
182         int& eu = g[i].end;
183         if(dis[eu] == (dis[node] + 1) && (f = blockedflow(eu, min(minf, g[i].cap - g[i].flow))) >= eps) {
184             minf -= f;
185             flow += f;
186             g[i].flow += f;
187             g[i ^ 1].flow -= f;
188             if(minf < eps)    return flow;
189         }
190     }
191     return flow;
192 }
193 
194 inline void init_dinic() {
195     vis = new boolean[(const int)(t + 1)];
196     dis = new int[(const int)(t + 1)];
197     cur = new int[(const int)(t + 1)];
198 }
199 
200 inline boolean dinic(double mid) {
201     mkmap(mid);
202     double maxflow = 0.0;
203     while(bfs()) {
204         for(int i = s; i <= t; i++)
205             cur[i] = m_begin(g, i);
206         maxflow += blockedflow(s, inf);
207     }
208     g.clear();
209     return dcmp(maxflow, sA);
210 } 
211 
212 inline void solve() {
213     init_dinic();
214     double l = 0.0, r = sA;
215     while(l + eps <= r) {
216         double mid = (l + r) / 2;
217         if(dinic(mid))    r = mid;
218         else l = mid;
219     }
220     printf("%.6lf", r);
221 }
222 
223 int main() {
224     init();
225     solve();
226     return 0;
227 }