SDOI2015 星际战争

拼搏现实的明天。 2021-09-30 12:14 242阅读 0赞

[题目传送门][Link 1]

这道题的m，n都非常的小，之后又看到……武器是可以连续攻击的，于是初步想到了网络流。

想到这道题是网络流之后，就很自然的想到应该在武器与机器人之间建边，在源点和武器之间建边，在机器人和汇点之间建边。

不过应该怎么建呢？我们知道武器可以连续攻击，就可以把武器的攻击看做水流，那么很显然，武器的攻击力乘以攻击的时间是武器一侧的流量限制，而机器人的生命值是机器人一侧的流量限制，而在武器和机器人之间没有流量限制，直接建容量为INF的边就可以了，因为前面原点一侧已经对其流量限制过了。

时间是我们要求的，所以我们可以进行二分答案，每次在二分的基础上建边，之后直接跑网络流，如果最大流等于机器人生命值之和说明跑完了，否则没跑完，这样二分即可。

注意因为精度要求是10^-4，所以可以直接把时间和机器人生命扩大10000倍，之后直接解决即可。

还有就是二分上界不要设的和INF一样大，否则会wa。

看一下代码。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<cmath>
    #include<set>
    #define rep(i,a,n) for(int i = a;i <= n;i++)
    #define per(i,n,a) for(int i = n;i >= a;i--)
    #define enter putchar('\n')
    using namespace std;
    typedef long long ll;
    const ll INF = 1e17;
    const int M = 40005;
    
    ll read()
    {
        ll ans = 0,op = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') op = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            ans *= 10;
            ans += ch - '0';
            ch = getchar();
        }
        return ans * op;
    }
    struct node
    {
        ll next,to,v;
    } e[M];
    ll deep[M],ecnt = -1,l,r = 1e16,n,m,a[M],b[M],g[60][60],mid;
    ll source = 199,sink = 200,cnt,head[M],maxflow,curr,cur[M];
    queue <int> q;
    void clear()
    {
        memset(e,0,sizeof(e));
        memset(head,-1,sizeof(head));
        memset(cur,0,sizeof(cur));
        ecnt = -1,cnt = 0,maxflow = 0,curr = 0;
    }
    void add(ll x,ll y,ll z)
    {
        e[++ecnt].to = y;
        e[ecnt].v = z;
        e[ecnt].next = head[x];
        head[x] = ecnt;
    }
    void build()
    {
        clear();
        rep(i,1,m) add(source,++cnt,mid * b[i]),add(cnt,source,0);
        rep(i,1,n) add(++cnt,sink,a[i] * 10000),add(sink,cnt,0),curr += a[i] * 10000;
        rep(i,1,m)
        rep(j,1,n)
        if(g[i][j]) add(i,j+m,INF),add(j+m,i,0);
    }
    bool bfs(ll s,ll t)
    {
        memset(deep,-1,sizeof(deep));
        while(!q.empty()) q.pop();
        rep(i,1,cnt) cur[i] = head[i];
        cur[source] = head[source],cur[sink] = head[sink];
        deep[s] = 0,q.push(s);
        while(!q.empty())
        {
            ll k = q.front();
            q.pop();
            for(int i = head[k]; i != -1; i = e[i].next)
            {
                if(deep[e[i].to] == -1 && e[i].v)
                {
                    deep[e[i].to] = deep[k] + 1;
                    q.push(e[i].to);
                }
            }
        }
        if(deep[t] != -1) return 1;
        else return 0;
    }
    ll dfs(ll s,ll t,ll limit)
    {
        if(!limit || s == t) return limit;
        for(int i = cur[s]; i != -1; i = e[i].next)
        {
            cur[s] = i;
            if(deep[e[i].to] != deep[s] + 1) continue;
            ll f = dfs(e[i].to,t,min(limit,e[i].v));
            if(f)
            {
                e[i].v -= f,e[i^1].v += f;
                return f;
            }
        }
        return 0;
    }
    bool dinic(ll s,ll t)
    {
        while(bfs(s,t)) maxflow += dfs(s,t,INF);
        if(maxflow == curr) return 1;
        else return 0;
    }
    int main()
    {
        n = read(),m = read();
        rep(i,1,n) a[i] = read();
        rep(i,1,m) b[i] = read();
        rep(i,1,m)
        rep(j,1,n) g[i][j] = read();
        while(l < r)
        {
            mid = l + r >> 1;
            build();
            if(dinic(source,sink)) r = mid;
            else l = mid + 1;
        }
        printf("%.6lf\n",(double)l / 10000.0);
        return 0;
    }

转载于:https://www.cnblogs.com/captain1/p/9495470.html

[Link 1]: https://www.luogu.org/problemnew/show/P3324