bzoj 4625 [BeiJing2016]水晶

内容

Description

不用惊慌，今天的题都不是小强出的。——融入了无数心血的作品，现在却不得不亲手毁掉，难以体会他的心情啊

。——那也是没有办法的事情，能量共振不消除的话……望着已经被装上炸药的水晶，02放下了望远镜，看向了手中的共振分析报告。还是会有一些水晶，幸存下来的……也许吧。地图由密铺的六边形单元组成，每个单元与其他六个单元相邻。为了方便起见，我们用坐标(x,y,z)描述一个单元的位置，表示从原点开始按如图所示的x,y,z方向各走若干步之后到达的地方。有可能有两个坐标描述同一个单元，比如(1,1,1)和(0,0,0)描述的都是原点

显然(x,y,z)单元和(x+1, y,z)，(x-1,y,z)，(x,y+1,z)，(x,y-1,z)，(x, y, z+1)，(x,y, z-1)相邻。有N块水晶位于地图的单元内，第i块水晶位于坐标(xi, yi, zi)所表示的单元中，并拥有ci的价值。每个单元内部可能会有多块水晶。地图中，有一些单元安装有能量源。如下图，任何满足x+y+z是3的整数倍的坐标所描述的单元内都安装有能量源。

有能量源的单元中的水晶价值将会额外增加10%.如果三块水晶所在的单元满足特定排列，那么它们将会引发共振。共振分两种，a共振和b共振。a共振：如果三块水晶所在的单元两两相邻地排成一个三角形，那么会引起a共振。

图中每一个三角形表示这三个单元各有一块水晶将会发生一个a共振。b共振：如果三块水晶所在的单元依次相邻地排成一条长度为2的直线段，且正中间的单元恰好有能量源，那么会引起b共振。

图中粉红色线段表示这三个单元各有一块水晶将会发生一个b共振，黑色线段表示即使这三个单元有水晶也不会发生b共振。现在你要炸掉一部分水晶，使得任何共振都不会发生的前提下，剩余水晶的价值总和最大。

Input

第一行是一个正整数N，表示水晶数量。
接下来N行，每行四个整数xi，yi，zi，ci，空格分隔，表示一个水晶的位
置和价值。有可能有水晶的位置重合。
N≤50000，1≤ci≤1000，|xi|, |yi|, |zi|≤1000.

Output

仅一行，一个实数，表示剩余水晶的价值总和。四舍五入保留1位小数。

Sample Input

4
0 0 0 11
1 0 0 5
0 1 0 7
0 0 -1 13

Sample Output

25.1

【样例说明1】

四块水晶排成一个菱形，没有b共振，有2处a共振，分别是1, 2, 4号水晶

和1, 3, 4号水晶形成的三角形。

因此，为了消除两处a共振，有如下3种方案：

因此，为了消除两处a共振，有如下3种方案

炸掉1号水晶，留下2, 3, 4号水晶，总剩余价值5+7+13=25.
炸掉4号水晶，留下1, 2, 3号水晶，总剩余价值11×(1+10%)+5+7=24.1.
炸掉2, 3号水晶，留下1, 4号水晶，总剩余价值11×(1+10%)+13=25.1.

因此我们采用第三种方案，最大总剩余价值为25.1.

题解

首先把显然可以把这图转换成一个二维的图。。

考虑每个在能量源的水晶，把无能量源的点黑白染色，则要不炸掉能量源，要不炸掉全黑，要不炸掉全白，离散变量有三个取值S=val>白=inf>A=1.1val>B=inf>黑=val>T。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#define N 100010
using namespace std;
const int inf = 0x3f3f3f3f;
struct flows {
    struct node {
        int to, next, flow;
    } e[N * 20];
    int tot, st[N], dis[N], cur[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, int z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, int z) {
//      printf("add%d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    int finds(int now, int T, int flow) {
        if (now == T)
            return flow;
        int f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    int dinic(int S, int T) {
        int flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
}flow;
int ge(int x, int y) { return (x + 2000) * 4000 + y + 2000; }
bool mark[N];
map <int, int> ma;
struct data {
    int x, y, z, c;
}a[N];
int n, ans;
bool ins(data p, int id) {
    int now = ge(p.x, p.y);
    if (ma[now])
        return a[ma[now]].c += p.c, 1;
    else
        return 0 * (ma[now] = id);
}
main() {
    scanf("%d", &n);
    int S = 0, T = 100001;
    flow.init();
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].z, &a[i].c), a[i].c *= 10;
        a[i].x -= a[i].z, a[i].y -= a[i].z, a[i].z = 0;
        if ((a[i].x + a[i].y) % 3 == 0) a[i].c += a[i].c / 10;
        if (ins(a[i], i)) mark[i] = 1;
        ans += a[i].c;
    }
    for (int i = 1; i <= n; ++i)
        if (!mark[i]) {
            flow.add_edge(i, i + n, a[i].c);
            if ((a[i].x + a[i].y + 30000) % 3 == 2)
                flow.add_edge(S, i, inf);
            if ((a[i].x + a[i].y + 30000) % 3 != 1) {
                flow.add_edge(i + n, ma[ge(a[i].x, a[i].y + 1)], inf);
                flow.add_edge(i + n, ma[ge(a[i].x + 1, a[i].y)], inf);
                flow.add_edge(i + n, ma[ge(a[i].x - 1, a[i].y - 1)], inf);
            } else {
                flow.add_edge(i + n, T, inf);
            }
        }
    printf("%.1lf", (double) (ans - flow.dinic(S, T)) / 10.0);
}