二分可以简化很多问题

懵逼的 题目

传送至 Luogu

扯淡的 题解

一开始以为有什么最大费用最小流什么的…
一不小心实在不会点开了标签…二分…Emmmmmmmm….

算法就很简单了…二分出一个时间, 然后按照时间连边:

  • S向激光枪连边, 容量为攻击力
  • 枪向可以攻击的人连边, 容量为INF
  • 人向T连边, 容量为装甲值

二分出解0ms稳如POI~

你以为就完了?

这里写图片描述

来告诉你什么叫卡 精 度

最后把eps设成0.00000000001…错的更多了…一气之下改成了LL…

由于这道题精度要求并不高, 而且装甲值不大, 那我们可以把 装甲值 * 10000, 然后直接用整数跑, 最后跑出来的答案除以 10000, 然后得出来比较稳健的答案, 在考场只能交一次的话还是把double转成 long long比较稳吧…但是一定要注意数据范围和精度乘起来不要超了long long…还有只要不爆空间能用long long还是用吧…可能一个关键的int就爆零了…

Update: 他们dalao管这个叫什么来着…是不是叫小数网络流来着…

沙茶的 代码

// 不算太毒瘤...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (1000 + 5)
#define MAXR (50 + 5)
#define MAXM (100000 + 5)
#define INF (0x7ffffffffffll)
#define eps (DD)(0.0000000001)
#define EPS (10000)
#define bh(a) ((a) + MAXR)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define DD double
#define LL long long
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
    LL flow;
    LL cap;
    edg() {}
    edg(int a, int b, int c, LL d): from(a), to(b), next(c), flow(0), cap(d) {}
} b[MAXM << 1];
int cntb;
int g[MAXN];

int nr, ng;
int att[MAXR], hp[MAXR], dis[MAXN];
LL sumr;
LL ans;
LL dinic(int, LL);
bool bfs();
bool pd(LL);
void solve();
void adn(int, int, LL);
int main()
{
    scanf("%d%d", &nr, &ng);
    for (int i = 1; i <= nr; i++)
    {
        int srx;
        scanf("%d", &srx);
        srx *= EPS;
        sumr += srx;
        adn(bh(i), t, srx);
        adn(t, bh(i), 0);
    }
    for (int i = 1; i <= ng; i++)
    {
        scanf("%d", &att[i]);
    }
    for (int i = 1; i <= ng; i++)
    {
        adn(s, i, 0);
        adn(i, s, 0);
        for (int j = 1; j <= nr; j++)
        {
            int srx;
            scanf("%d", &srx);
            if (srx)
            {
                adn(i, bh(j), INF);
                adn(bh(j), i, 0);
            }
        }
    }
    solve();
    printf("%lf", (DD)ans / EPS);
    return 0;
}
LL dinic(int dq, LL maxf)
{
    if (dq == t || !maxf)
        return maxf;
    LL re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (dis[b[i].to] == dis[dq] + 1 && b[i].cap > b[i].flow)
        {
            LL zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            maxf -= zl;
            re += zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }
    }
    return re;
}
bool bfs()
{
    queue<int> q;
    memset(dis, 0, sizeof(dis));
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (b[i].cap - b[i].flow > eps && !dis[b[i].to])
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
bool pd(LL cap)
{
    for (int i = 1; i <= cntb; i++)
        b[i].flow = 0;
    for (int i = g[s]; i; i = b[i].next)
    {
        b[i].cap = cap * att[b[i].to];
    }
    LL  re = 0;
    while (bfs())
        re += dinic(s, INF);
    return sumr == re;
}
void solve()
{
    LL le = 0, ri = INF;
    while (ri > le)
    {
        LL mi = (le + ri) >> 1;
        if (pd(mi))
        {
            ans = mi;
            ri = mi;
        }
        else
            le = mi + 1;
    }
}
void adn(int from, int to, LL cap)
{
    b[++cntb] = edg(from, to, g[from], cap);
    g[from] = cntb;
}
/*
2 2
2 1 
6 6 
1 1 
0 1
*/

By 感觉OK的 Cansult