bzoj 5403 Marshland

$n \leq 50$

sol：

放一个在 $x$ 处拐弯的 $L$ 形石头相当于在水平和垂直方向上各选一个与 $x$ 相邻的点，全局不能重复选

最小化危险度，相当于满足这些限制的情况下石头盖住的点危险度越大越好，而石头有各种各样的限制，考虑费用流

这是一个“只能增广 m 次的最大费用可行流”问题，我们增广到 m 次或者找出来的最长路为负即可

为了满足“不重复选”，可以拆点，每个入点向出点连流量 1，费用为危险度的边

因为每个危险点左右和上下各能选一个，相当于“每头牛都要分到一瓶可乐和一份午饭”（忘了这道题题号了...），可以把每个不危险的点分成“可乐”和“午饭”两类

因为选的两个不危险的点行数奇偶性不同，所以可以考虑按行数奇偶把非危险点分成两类

$S \space \rightarrow \space 每个行数为奇数的非危险点 \space \rightarrow \space 相邻的入点$

$相邻的出点 \space \rightarrow \space 每个行数为偶数的非危险点 \space \rightarrow \space T$

以上两类边流量 1，费用 0

然后愉快的流

#include<bits/stdc++.h>

#define LL long long

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

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

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = ,maxm = ,oo = ;

struct ZKW

{

    int head[maxn], nx[maxn], inq[maxn], vis[maxn], dis[maxn];

    int n, m, s, t, ans, cost;

    queue<int> q;

    struct Edge

    {

        int from, to, caps, cost;

        Edge(){}

        Edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), caps(_3), cost(_4){}

    }es[maxm];

    ZKW(){memset(head, -, sizeof(head));}

    void setn(int _){n = _;}

    void AddEdge(int u, int v, int w, int c)

    {

        es[m] = Edge(u, v, w, c); nx[m] = head[u]; head[u] = m++;

        es[m] = Edge(v, u, , -c); nx[m] = head[v]; head[v] = m++;

    }

    bool BFS()

    {

        for(int i = ;i <= n;i++)dis[i] = -oo;

        dis[t] = ;inq[t] = ;q.push(t);

        while(!q.empty())

        {

            int now = q.front();q.pop();

            for(int i = head[now]; i != -; i = nx[i])

            {

                Edge& e = es[i^];

                if(e.caps && dis[e.from] < dis[now] + e.cost)

                {

                    dis[e.from] = dis[now] + e.cost;

                    if(!inq[e.from])

                    {

                        inq[e.from] = ;

                        q.push(e.from);

                    }

                }

            }

            inq[now] = ;

        }

        if(dis[s] > ){cost = dis[s];return ;}

        return ;

    }

    int DFS(int u, int a)

    {

        if(u == t || !a)return ans += cost * a, a;

        if(vis[u])return ; vis[u] = ;

        int flow = , f;

        for(int i = head[u]; i != -; i = nx[i])

        {

            Edge& e = es[i];

            if(dis[e.to] == dis[u] - e.cost && (f = DFS(e.to, min(e.caps, a))))

            {

                e.caps -= f; es[i^].caps += f;

                a -= f; flow += f;

                if(!a)return flow;

            }

        }

        return flow;

    }

    int MaxCostFlow(int _s, int _t, int tms)

    {

        s = _s, t = _t;

        int flow = , f;

        for(int i = ; i <= tms; i++) if(BFS()) {memset(vis, , sizeof(vis)); flow += DFS(s, oo);}

        return flow;

    }

} sol;

int n, m, k, s, t, ans;

int mat[][],mem[][][],dfn,b[maxn];

inline int pos(int x, int y, int type)

{

    return n * n * (type - ) + (x - ) * n + y;

}

int main()

{

    n = read(), m = read(), k = read();

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

        for(int j = ; j <= n; j++) mat[i][j] = read();

    s = , t = n * n *  + ;

    sol.setn(t + );

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

    {

        int x = read(), y = read();

        b[pos(x, y, )] = ;

    }

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

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

        {

            ans += mat[i][j];

            if(b[pos(i, j, )])continue;

            if((i + j) & )

                sol.AddEdge(pos(i, j, ), pos(i, j, ), , mat[i][j]);

            else

            {

                if(i & )

                {

                    sol.AddEdge(s, pos(i, j, ), , );

                    if(i > ) sol.AddEdge(pos(i, j, ), pos(i - , j, ), , );

                    if(j > ) sol.AddEdge(pos(i, j, ), pos(i, j - , ), , );

                    if(i < n) sol.AddEdge(pos(i, j, ), pos(i + , j, ), , );

                    if(j < n) sol.AddEdge(pos(i, j, ), pos(i, j + , ), , );

                }

                else

                {

                    sol.AddEdge(pos(i, j, ), t, , );

                    if(i > ) sol.AddEdge(pos(i - , j, ),pos(i, j, ), , );

                    if(j > ) sol.AddEdge(pos(i, j - , ),pos(i, j, ), , );

                    if(i < n) sol.AddEdge(pos(i + , j, ), pos(i, j, ), , );

                    if(j < n) sol.AddEdge(pos(i, j + , ), pos(i, j, ), , );

                }

            }

        }

    sol.MaxCostFlow(s, t, m);

    cout << ans - sol.ans << endl;

}

不知道为什么在限制增广次数的时候 ZKW 的多路增广是错的

巴特西

bzoj 5403 Marshland

最新文章

热门文章