JZOJ 5057 炮塔

根据 RHX 大佬的名言：「看到这种有奇怪限制，正常人做不出来的题，就可以考虑网络流。」

看起来像费用流，但是并布星（
注意到相交可以看做连通，于是可以往最小割的方向考虑。

建图的大体思想是横纵连的方向要相反，割一条边相当于打到某个位置。
具体可参见代码。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define id(x,y,k) (2 * ((x - 1) * m + y) + k - 1)
using namespace std;
const int N = 50;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = { 0, 0,-1, 1};
int n,m,s,t;
int a[N + 5][N + 5],ans;
namespace Dinic
{
    const int N = 5002;
    const int M = 1e5;
    int n;
    int to[(M << 1) + 5],val[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5],cur[N + 5],edge_tot;
    inline int init()
    {
        memset(first,-1,sizeof first);
        return 0;
    }
    int Init = init();
    inline void add_edge(int u,int v,int w)
    {
        int &tot = edge_tot;
        to[tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot++;
    }
    inline void add(int u,int v,int w)
    {
        add_edge(u,v,w),add_edge(v,u,0);
    }
    int head,tail,q[N + 5],dep[N + 5],vis[N + 5];
    int bfs()
    {
        head = tail = 0;
        memset(vis,0,sizeof vis);
        memset(dep,0x3f,sizeof dep);
        dep[s] = 0,vis[s] = 1,q[++tail] = s;
        while(head < tail)
        {
            int p = q[++head];
            vis[p] = 0;
            for(register int i = first[p];~i;i = pre[i])
                if(val[i] && dep[to[i]] > dep[p] + 1)
                {
                    dep[to[i]] = dep[p] + 1;
                    if(!vis[to[i]])
                        vis[to[i]] = 1,q[++tail] = to[i];
                }
        }
        return dep[t] ^ 0x3f3f3f3f;
    }
    int maxflow;
    int dfs(int p,int flow)
    {
        if(p == t)
            return (maxflow += flow,flow);
        int ret = 0,used = 0;
        for(register int &i = cur[p];~i;i = pre[i])
            if(val[i] && dep[to[i]] == dep[p] + 1 && (ret = dfs(to[i],min(flow - used,val[i]))))
            {
                used += ret,val[i] -= ret,val[i ^ 1] += ret;
                if(used >= flow)
                    break;
            }
        return used;
    }
    int dinic()
    {
        while(bfs())
            memcpy(cur,first,sizeof cur),dfs(s,0x3f3f3f3f);
        return maxflow;
    }
}
int main()
{
    freopen("tower.in","r",stdin),freopen("tower.out","w",stdout);
    scanf("%d%d",&n,&m),s = 2 * n * m + 1,t = 2 * n * m + 2,Dinic::n = 2 * n * m + 2;
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j)
            scanf("%d",a[i] + j),Dinic::add(id(i,j,0),id(i,j,1),0x3f3f3f3f);
    for(register int i = 1;i <= n;++i)
        for(register int j = 1,d,x,y,nx,ny,mx;j <= m;++j)
            if(a[i][j] < 0)
            {
                d = -1 - a[i][j],mx = 0;
                for(x = i,y = j;;x = nx,y = ny)
                {
                    nx = x + dx[d],ny = y + dy[d];
                    if(nx < 1 || nx > n || ny < 1 || ny > m)
                        break;
                    mx = max(mx,a[nx][ny]);
                }
                ans += mx;
                if(d < 2)
                {
                    Dinic::add(s,id(i,j,0),mx);
                    for(x = i,y = j;;x = nx,y = ny)
                    {
                        nx = x + dx[d],ny = y + dy[d];
                        if(nx < 1 || nx > n || ny < 1 || ny > m)
                            break;
                        Dinic::add(id(x,y,0),id(nx,ny,0),mx - max(a[x][y],0));
                    }
                }
                else
                {
                    Dinic::add(id(i,j,1),t,mx);
                    for(x = i,y = j;;x = nx,y = ny)
                    {
                        nx = x + dx[d],ny = y + dy[d];
                        if(nx < 1 || nx > n || ny < 1 || ny > m)
                            break;
                        Dinic::add(id(nx,ny,1),id(x,y,1),mx - max(a[x][y],0));
                    }
                }
            }
    ans -= Dinic::dinic();
    printf("%d\n",ans);
}