【luogu4474王者之剑】--网络流

题目描述

这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。
宝石排列在一个n*m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。
开始时刻为0秒。以下操作，每秒按顺序执行

在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格（x,y）上，她可以拿走（x，y）中的宝石。
在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失
若阿尔托利亚·潘德拉贡第i秒开始时在方格（x，y）上，则在第i+1秒可以立即移动到（x+1，y），（x，y+1），（x-1，y）或（x，y-1）上，也可以停留在（x,y)上。

求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

输入格式

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

输出格式

输出最多可以拿到多少价值宝石

输入输出样例

输入 #1

输出 #1

说明/提示

姚金宇的原创题。

代码：

include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define R register

#define inf 1e9+7

using namespace std;

const int Excalibur = 10005;//N或MAXN

int n, m, S, T, cur[Excalibur], dep[Excalibur];

struct saber {//edge，我的王

    int nxt, to, v;

}rin[Excalibur<<3];//是凛哦

int Lancer[Excalibur], Fate = 1, Archar;//emmm，head和tot以及sum

int x[5] = {0, -1, 0, 1, 0}, y[5] = {0, 0, -1, 0, 1};

inline void add(int from, int to, int v) {

    rin[++Fate].v = v;

    rin[Fate].to = to;

    rin[Fate].nxt = Lancer[from];

    Lancer[from] = Fate;

}

inline bool bfs(int s, int t) {

    queue<int> Rider;//q

    for(R int i = 0;i <= T;++ i) cur[i] = Lancer[i], dep[i] = 0;

    Rider.push(s); dep[s] = 1;

    while(!Rider.empty()) {

        R int vi = Rider.front();

        Rider.pop();

        for(R int i = Lancer[vi]; i ;i = rin[i].nxt) {

            R int vc = rin[i].to;

            if(!dep[vc] && rin[i].v) {

                dep[vc] = dep[vi] + 1;

                Rider.push(vc);

            }

        }

    }

    return dep[t];

}

int dfs(int s, int t, int flow) {

    if(!flow || s == t) return flow;

    int Caster = 0, Assassin;//增量

    for(R int i = cur[s]; i ;i = rin[i].nxt) {

        R int vc = rin[i].to;

        cur[s] = i;

        if(dep[vc] == dep[s] + 1 && rin[i].v) {

            Assassin = dfs(vc, t, min(flow, rin[i].v));

            if(!Assassin) continue;

            Caster += Assassin; flow -= Assassin;

            rin[i].v -= Assassin; rin[i ^ 1].v += Assassin;

            if(!flow) return Caster;

        }

    }

    return Caster;

}

int Dinic() {

    int res = 0;

    while(bfs(S, T)) res += dfs(S, T, inf);

    return Archar - res;

}

int main() {

    scanf("%d%d",&n, &m);

    //以下是建图，中二到此结束

    S = 0, T = n * m + 1;

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

        for(R int j = 1;j <= m;++ j) {

            R int v; scanf("%d",&v);

            Archar += v;

            R int p = (i - 1) * m + j;

            if((i + j) & 1) { add(S, p, v);add(p, S, 0); }

            else { add(p, T, v);add(T, p, 0); }

        }

    for(R int i = 1;i <= n;++ i) for(R int j = 1;j <= m;++ j)

        if((i + j) & 1)

            for(R int k = 1;k <= 4;++ k) {

                R int f = i + x[k], g = j + y[k];

                if(f < 1 || f > n || g < 1 || g > m) continue;

                R int u = (i - 1) * m + j, v = (f - 1) * m + g;

                add(u, v, inf); add(v, u, 0);

            }

    printf("%d",Dinic());

    return 0;

}

巴特西