[SDOI 2015] 星际战争

[题目链接]

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

[算法]

首先发现问题具有单调性 ， 不妨二分答案mid

考虑网络流 :

将源点向每个"激光武器”连一条流量为mid * Bi的边

将每个“激光武器”向每个其可以攻击的“机器人”连一条流量为正无穷的边

将每个“机器人”向汇点连一条流量为Ai的边

判断是否满流即可

时间复杂度 : O(dinic(N + M , M ^ 2) * logV)

[代码]

为避免精度误差 ， 可以在整数域上进行二分 ， 最后以浮点数形式输出

#include<bits/stdc++.h>

using namespace std;

#define N 510

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const ll inf = 1e15;

struct edge

{

        int to;

        ll w;

        int nxt;

} e[N * N * ];

int n , m , tot , S , T;

int dep[N] , head[N] , g[N][N];

ll a[N] , b[N];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void addedge(int u , int v , ll w)

{

        ++tot;

        e[tot] = (edge){v , w , head[u]};

        head[u] = tot;

        ++tot;

        e[tot] = (edge){u ,  , head[v]};

        head[v] = tot;

}

inline bool bfs()

{

        queue< int > q;

        for (int i = ; i <= T; ++i)

                dep[i] = -;

        q.push(S);

        dep[S] = ;

        while (!q.empty())

        {

                int cur = q.front();

                q.pop();

                for (int i = head[cur]; i; i = e[i].nxt)

                {

                        int v = e[i].to;

                        ll w = e[i].w;

                        if (w >  && dep[v] == -)

                        {

                                dep[v] = dep[cur] + ;

                                q.push(v);

                                if (v == T) return true;

                        }

                }

        }

        return false;

}

inline ll dinic(int u , ll flow)

{

        ll k , rest = flow;

        if (u == T)

                return flow;

        for (int i = head[u]; i && rest; i = e[i].nxt)

        {

                int v = e[i].to;

                ll w = e[i].w;

                if (dep[v] == dep[u] +  && w)

                {

                        k = dinic(v , min(w , rest));

                        e[i].w -= k;

                        e[i ^ ].w += k;

                        if (!k) dep[v] = ;

                        rest -= k;

                }

        }

        return flow - rest;

}

inline bool check(ll mid)

{

        S = n + m +  , T = S + ;

        for (int i = ; i <= T; ++i) head[i] = ;

        for (int i = ; i <= tot; ++i) e[i].nxt = ;

        tot = ;

        for (int i = ; i <= m; ++i) addedge(S , i , b[i] * mid);

        for (int i = ; i <= m; ++i)

        {

                for (int j = ; j <= n; ++j)

                {

                        if (g[i][j])

                                addedge(i , j + m , inf);

                }

        }

        ll sum = ;

        for (int i = ; i <= n; ++i)

        {

                addedge(i + m , T , a[i]);

                sum += a[i];

        }

        ll res = ;

        while (bfs())

        {

                while (double flow = dinic(S , inf)) res += flow;

        }

        return res == sum;

}

int main()

{

        scanf("%d%d" , &n , &m);

        for (int i = ; i <= n; ++i)

        {

                scanf("%lld" , &a[i]);

                a[i] *= ;

        }

        for (int i = ; i <= m; ++i) scanf("%lld" , &b[i]);

        for (int i = ; i <= m; ++i)

        {

                for (int j = ; j <= n; ++j)

                {

                        scanf("%d" , &g[i][j]);

                }

        }

        ll l =  , r = inf , ans = ;

        while (l <= r)

        {

                int mid = (l + r) >> ;

                if (check(mid))

                {

                        ans = mid;

                        r = mid - ;

                } else l = mid + ;

        }

        printf("%.6lf\n" , (double)(ans / 1000.0));

        return ;

}