2 条题解
-
1
chenjuncong LV 7 @ 2016-02-17 19:11:43
doc,,,你的数据有毒吧,,,
-
02025-06-13 16:04:21@
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define forU(i, a, b) for (int i = (a), UP = (b); i <= UP; ++i) #define forD(i, a, b) for (int i = (a), DOWN = (b); i >= DOWN; --i) using namespace std; inline double fabs(double x) {return x < 0 ? -x : x;} const int N = 55; const int M = N * N * 2; struct node { int nxt, to; double c; node(int _nxt = 0, int _to = 0, double _c = 0) : nxt(_nxt), to(_to), c(_c) {} } E[M]; int cnt, point[N << 1], cur[N << 1]; void ins(int u, int v, double c) { E[++cnt] = node(point[u], v, c); point[u] = cnt; E[++cnt] = node(point[v], u, 0); point[v] = cnt; } bool can[N][N]; int q[N << 1], n, m, S, T, d[N << 1]; double A[N], B[N]; bool BFS() { memset(d, 0, sizeof(int) * (T + 1)); int head = 0, tail = 1, u, v; q[1] = S; d[S] = 1; while (head != tail) { u = q[++head]; for (int i = point[u]; i; i = E[i].nxt) if (fabs(E[i].c) > 1e-12 && !d[v = E[i].to]) { d[v] = d[u] + 1; q[++tail] = v; } } return d[T]; } double DFS(int u, double a) { if (fabs(a) < 1e-12 || u == T) return a; double f, flow = 0; for (int &i = cur[u]; i; i = E[i].nxt) if (d[E[i].to] == d[u] + 1 && fabs(f = DFS(E[i].to, min(a, E[i].c))) > 1e-12) { a -= f; flow += f; E[i].c -= f; E[i ^ 1].c += f; if (fabs(a) < 1e-12) break; } return flow; } double Dinic() { double flow = 0; while (BFS()) { memcpy(cur, point, sizeof(int) * (T + 1)); flow += DFS(S, 100000000000000.0); } return flow; } double tot = 0; bool can2(double tim) { memset(point, 0, sizeof(int) * (T + 1)); cnt = 1; forU (i, 1, m) { ins(S, i, tim * B[i]); forU (j, 1, n) if (can[i][j]) ins(i, j + m, 100000000000000.0); } forU (i, 1, n) ins(i + m, T, A[i]); return fabs(Dinic() - tot) < 1e-5; } int main() { scanf("%d%d", &n, &m); S = n + m + 1; T = S + 1; forU (i, 1, n) scanf("%lf", A + i), tot += A[i]; forU (i, 1, m) scanf("%lf", B + i); int num; double left = 0, right = 0, mid; forU (i, 1, m) forU (j, 1, n) { scanf("%d", &num); can[i][j] = num; } forU (i, 1, n) { double fornow = 0; forU (j, 1, m) fornow = max(fornow, B[j]); right += ceil(A[i] / fornow); } while (right - left > 1e-5) { mid = (left + right) / 2.0; if (can2(mid)) right = mid; else left = mid; } printf("%.3lf\n", left); return 0; }
- 1
信息
- ID
- 1948
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 187
- 已通过
- 16
- 通过率
- 9%
- 被复制
- 2
- 上传者