题解

2 条题解

  • 1
    @ 2016-02-17 19:11:43

    doc,,,你的数据有毒吧,,,

  • 0
    @ 2025-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
上传者