Solution

https://blog.csdn.net/qq_33229466/article/details/70159372

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100000;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int a[100][100];
int go[5][2] = {{},{-1, 0},{1, 0},{0,-1},{0,1}};
int head[N], nex[N], to[N], c[N], ce = 1;
void add(int u, int v, int w) {
    to[++ce] = v; nex[ce] = head[u]; head[u] = ce; c[ce] = w;
    to[++ce] = u; nex[ce] = head[v]; head[v] = ce; c[ce] = 0;
}
int point(int x, int y, int k) {
    return (x - 1) * m + y + (k - 1) * n * m;
}
bool check(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
int d[N];
queue<int> q;
bool bfs() {
    memset(d, -1, sizeof d);
    d[s] = 0; q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=nex[i]) {
            int v = to[i];
            if(c[i] && d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return d[t] != -1;
}
int dfs(int u, int flow) {
    if(u == t) return flow;
    int res = 0;
    for(int i=head[u]; i; i=nex[i]) {
        int v = to[i];
        if(c[i] && d[v] == d[u] + 1) {
            int tmp = dfs(v, min(flow, c[i]));
            c[i] -= tmp; c[i^1] += tmp;
            flow -= tmp; res += tmp;
            if(flow == 0) break;
        }
    }
    if(res == 0) d[u] = -1;
    return res;
}
int maxflow() {
    int res = 0;
    while(bfs()) res += dfs(s, INF);
    return res;
}
int main() {
    scanf("%d%d", &n, &m);
    s = 2 * n * m + 1; t = s + 1;
    for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++)
        scanf("%d", &a[i][j]);
    int ans = 0;
    for(int x=1; x<=n; x++) {
        for(int y=1; y<=m; y++) {
            add(point(x, y, 1), point(x, y, 2), INF);
            int opt = -a[x][y];
            if(opt <= 0) continue;
            if(opt <= 2) add(s, point(x, y, 1), INF);
            else add(point(x, y, 2), t, INF);
            int maxv = 0, px, py;
            for(int tx=x, ty=y; check(tx, ty); tx+=go[opt][0], ty+=go[opt][1]) {
                if(a[tx][ty] > maxv) {
                    maxv = a[tx][ty];
                    px = tx; py = ty;
                }
            }
            ans += maxv;
            for(int tx=x, ty=y; tx!=px||ty!=py; tx+=go[opt][0], ty+=go[opt][1]) {
                if(!check(tx, ty)) break;
                int ttx = tx + go[opt][0], tty = ty + go[opt][1];
                if(opt <= 2) add(point(tx, ty, 1), point(ttx, tty, 1), maxv-max(0,a[tx][ty]));
                else add(point(ttx, tty, 2), point(tx, ty, 2), maxv-max(0,a[tx][ty]));
            }
        }
    }
    printf("%d\n", ans - maxflow());
    return 0;
}

Description

Nick最近在玩一款很好玩的游戏,游戏规则是这样的:
有一个n*m的地图,地图上的每一个位置要么是空地,要么是炮塔,要么是一些BETA狗,Nick需
要操纵炮塔攻击BETA狗们。
攻击方法是:对于每个炮塔,游戏系统已经给出它可以瞄准的方向(上下左右其中一个),Nick需要
选择它的攻击位置,每一个炮塔只能够攻击一个位置,炮塔只能够向着它的瞄准方向上的某个位置发
动攻击,当然炮塔也可以不进行攻击。炮塔威力强大,它可以且仅可以消灭目标位置上所有的BETA狗。
出于安全考虑,游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔,即对于任意一个炮
塔,它所有可能的攻击位置上不存在另外一个炮塔。而且,如果把炮塔的起点和终点称为炮弹的运行
轨迹,那么系统不允许两条轨迹相交f包括起点和终点)。
现在,选定目标位置以后,每一个炮塔同时开炮,你要告诉Nick,他最多可以干掉多少BETA狗。

Input

第一行两个正整数n,m,表示地图的规模。
接下来礼行,每行m个整数,0表示空地,-1,-2,一3,-4分别表示瞄准上下左右的炮塔,若为正整
数p,则表示该位置有p个BETA狗。
n,m <= 50,每个位置的BETA狗数量不超过999个,保证不存在任意一个炮塔能够瞄准另外一个炮塔

Output

一个正整数,表示Nick最多可以干掉几个BETA狗

Sample Input

3 2
0 9
-4 3
0 -1

Sample Output

9