【Luogu-P3324 [SDOI2015] / DSY-1993】星际战争

· · 个人记录

传送门：P3324 [SDOI2015]星际战争

二分 + 最大流

\mathfrak{Solution}

1

不可否认，看到题面的第一反应是构造二分图，让武器在一边，机器人在另一边，武器连向自己可以攻击的机器人。

然后边的费用就是该武器灭掉这个机器人所用的时间，最后跑费用流。

但这个想法太 \text{naive} 了，是错的。因为答案是一个实数，而且武器的攻击是连续的，所以万万不可绝对地将时间设为费用。

2

既然时间不能为费用，那不妨来一个大胆的想法：将时间当做流量。

二分答案，即消灭掉所有机器人所用时间，然后建边：

在此基础上，跑一边最大流。若最大流小于所有机器人生命值之和，则 l = mid + 1;，否则 r = mid;。

3

因为题目要求精确到 10^{-3}，所以将每个机器人生命值乘上 10^3，最后输出答案的时候再除回来即可。

\mathfrak{Code}

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define maxn 205
#define maxm 10000
#define inf 100000000000

int n, m;
int a[maxn], b[maxn];
int sum;
bool at[maxn][maxn];
int l, r = 1e10, mid;
int cnt = 1, hd[maxn];
int dep[maxn];
struct node{
    int to, nxt, flw;
}e[maxm];
int s, t;

inline void add(int u, int v, int f)
{
    e[++cnt] = (node){v, hd[u], f};
    hd[u] = cnt;
    e[++cnt] = (node){u, hd[v], 0};
    hd[v] = cnt;
}

inline void build(int tt)
{
    rep(i, 1, m) add(s, i, tt * b[i]);
    rep(i, 1, n) add(i + m, t, a[i]);
    rep(i, 1, m) rep(j, 1, n) 
        if(at[i][j]) add(i, m + j, inf);
}

inline bool bfs()
{
    queue <int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1, q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v, i = hd[u]; i; i = e[i].nxt)
        {
            if(e[i].flw and !dep[v = e[i].to]) 
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }       
        }
    }
    if(dep[t]) return 1;
    return 0;
}

inline int dfs(int u, int in)
{
    if(u == t) return in;
    int out = 0;
    for(int i = hd[u]; i and in; i = e[i].nxt)
    {
        int v = e[i].to;
        if(dep[v] == dep[u] + 1 and e[i].flw)
        {   
            int res = dfs(v, min(e[i].flw, in));
            e[i].flw -= res, e[i ^ 1].flw += res;
            in -= res, out += res;
        }                                                                                                                
    }
    if(!out) dep[u] = 0;
    return out;
}

inline int dinic()
{
    int ans = 0;
    while(bfs()) ans += dfs(s, inf);
    return ans;
}

signed main()
{
    scanf("%d%d", &n, &m);
    t = n + m + 1;
    rep(i, 1, n) 
        scanf("%d", &a[i]), a[i] *= 1000ll, sum += a[i];
    rep(i, 1, m) scanf("%d", &b[i]);
    rep(i, 1, m) rep(j, 1, n) scanf("%d", &at[i][j]);
    while(l < r)
    {
        mid = (l + r) >> 1ll;
        memset(hd, 0, sizeof hd), cnt = 1;
        build(mid);
        if(dinic() < sum) l = mid + 1;
        else r = mid; 
    }
    printf("%.4lf", (double) l / 1000.0);
    return 0;
}

——\mathfrak{End}——