(BZOJ) 3993: [SDOI2015]星际战争

http://www.lydsy.com/JudgeOnline/problem.php?id=3993

最近真的一直在耍智障>< 一些很簡單的題目都想不太出來><

對答案作二分搜，注意到每個激光武器的攻擊量是一樣的。

所以，假設現在搜到mid，則：源點s --> 每個激光武器，流量 = t * b[i]

每個機器人 --> 匯點t，流量 = a[i]

如果激光武器 i 可以攻擊 機器人 j ，則 i-->j ，流量= a[i]

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

#define SZ(x) ((int)(x).size())

typedef long double ld;
const ld eps = 1e-9;

bool eq(ld a,ld b)
{
    return fabs(a-b) <= eps;
}

struct Dinic
{
    static const int N = 106;
    struct Edge
    {
        int to;
        ld cap;
        int rev;
        Edge(){}
        Edge(int _to,ld _cap,int _rev)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
        }
    };
    vector<Edge> G[N];
    void add_edge(int from,int to,ld cap)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to])));
        G[to].push_back(Edge(from,0,SZ(G[from])-1));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int level[N],iter[N];
    void BFS()
    {
        memset(level,-1,sizeof(level));
        level[s]=0;
        queue<int> que;
        que.push(s);
        while (!que.empty())
        {
            int t=que.front();
            que.pop();
            for (int i=0;SZ(G[t])>i;i++)
            {
                Edge e=G[t][i];
                if (!eq(e.cap,0) && level[e.to] == -1)
                {
                    level[e.to] = level[t] +1;
                    que.push(e.to);
                }
            }
        }
    }
    ld dfs(int now, ld flow)
    {
        if (now == t) return flow;
        for (int &i=iter[now];SZ(G[now])>i;i++)
        {
            Edge &e = G[now][i];
            if (!eq(e.cap,0) && level[e.to] == level[now] + 1)
            {
                ld ret = dfs(e.to,min(flow,e.cap));
                if (!eq(ret,0))
                {
                    e.cap -= ret;
                    G[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    ld flow()
    {
        ld ret=0;
        while (true)
        {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            ld tmp=0;
            while (!eq(0, (tmp = dfs(s,1e20)) ))
            {
                ret += tmp;
            }
        }
        return ret;
    }
} kirino;

const int N = 56;

int a[N];
int b[N];
int can[N][N];

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]); //robot blood
    }
    for (int i=1;m>=i;i++)
    {
        scanf("%d",&b[i]); //weapon cost
    }
    for (int i=1;m>=i;i++)
    {
        for (int j=1;n>=j;j++)
        {
            scanf("%d",&can[i][j]);  //weapon i can beat robot j
        }
    }
    ld L=0,R=1e10;
    int cnt=100;
    int s=0,t=n+m+1;
    while (cnt--)
    {
        ld mid = (L+R)/2;
        kirino.init(t,s,t);
        for (int i=1;m>=i;i++)
        {
            kirino.add_edge(s,i,b[i]*mid);
        }
        ld tot=0;
        for (int i=1;n>=i;i++)
        {
            kirino.add_edge(i+m,t,a[i]);
            tot += a[i];
        }
        for (int i=1;m>=i;i++)
        {
            for (int j=1;n>=j;j++)
            {
                if (can[i][j])
                {
                    kirino.add_edge(i,j+m,a[j]);
                }
            }
        }
        ld ret = kirino.flow();
        if (eq(ret,tot)) R=mid;
        else L=mid;
    }
    double ans=R;
    printf("%.10f\n",ans);
}