[BZOJ4625][BeiJing2016]水晶
试题描述
不用惊慌，今天的题都不是小强出的。——融入了无数心血的作品，现在却不得不亲手毁掉，难以体会他的心情啊
。——那也是没有办法的事情，能量共振不消除的话……望着已经被装上**的水晶，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共振。现在你要炸掉一部分水晶，使得任何共振都不会发生的前提下，剩余水晶的价值总和最大。
输入
第一行是一个正整数N，表示水晶数量。
接下来N行，每行四个整数xi，yi，zi，ci，空格分隔，表示一个水晶的位
置和价值。有可能有水晶的位置重合。
N≤50000，1≤ci≤1000，|xi|, |yi|, |zi|≤1000.
输出
仅一行，一个实数，表示剩余水晶的价值总和。四舍五入保留1位小数。
输入示例
4 0 0 0 11 1 0 0 5 0 1 0 7 0 0 -1 13
输出示例
25.1
数据规模及约定
见“输入”
题解
我们发现两种共振的情况都包含且仅包含了一个能量源，那么我们把能量源的六边形先盖住不看，剩下的六边形的相邻关系构成了一个二分图，我们对这个二分图进行黑白染色，发现这两种共振都包含了一黑一白。
于是得出结论：对于相邻的黑、白和能量源我们要么不选能量源，黑白任意；要么选能量源和同色的。
于是建出最小割模型：源点向白点连容量为权值的边；每个能量源拆成两个点 A 和 B，相邻的白点向 A，B 向相邻的黑点连无穷的边，A 向 B 连权值 × 1.1 的边；黑点向汇点连容量为权值的边。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 600010
#define maxx 4010
#define oo 2147483647
#define pii pair <int, int>
struct Edge {
int from, to, flow;
Edge() {}
Edge(int _1, int _2, int _3): from(_1), to(_2), flow(_3) {}
};
struct Dinic {
int n, m, s, t, head[maxn], nxt[maxm];
Edge es[maxm];
int Q[maxn], hd, tl, vis[maxn];
int cur[maxn];
void init() {
m = 0; memset(head, -1, sizeof(head));
return ;
}
void setn(int _) { n = _; return ; }
void AddEdge(int a, int b, int c) {
es[m] = Edge(a, b, c); nxt[m] = head[a]; head[a] = m++;
es[m] = Edge(b, a, 0); nxt[m] = head[b]; head[b] = m++;
return ;
}
bool BFS() {
memset(vis, 0, sizeof(vis));
hd = tl = 0; Q[++tl] = s;
vis[s] = 1;
while(hd < tl) {
int u = Q[++hd];
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(e.flow && !vis[e.to]) {
vis[e.to] = vis[u] + 1;
Q[++tl] = e.to;
}
}
}
return vis[t] > 0;
}
int DFS(int u, int a) {
if(u == t || !a) return a;
int f, flow = 0;
for(int& i = cur[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(vis[e.to] == vis[u] + 1 && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s; t = _t;
int flow = 0;
while(BFS()) {
for(int i = 1; i <= n; i++) cur[i] = head[i];
flow += DFS(s, oo);
}
return flow;
}
} sol;
int Cnt;
struct Node {
int id, x, y;
int val;
Node(): id(0) {}
Node(int _1, int _2, int _3): id(0), x(_1), y(_2), val(_3) {}
int p() { return id ? id : id = ++Cnt; }
} ns[maxn], n2[maxn], Source, Tank;
vector <int> white, black, middle;
int Map[maxx][maxx], Mid[maxx][maxx];
void add(vector <int>& A, int x, int y) {
if(0 <= x && x < maxx && 0 <= y && y < maxx) ;
else return ;
if(Mid[x][y]) A.push_back(Mid[x][y]);
return ;
}
void add_white(int x, int y) {
if(0 <= x && x < maxx && 0 <= y && y < maxx) ;
else return ;
add(white, x - 1, y);
add(white, x, y - 1);
add(white, x + 1, y + 1);
int u = Mid[x][y];
if(Mid[x-1][y]) sol.AddEdge(ns[Mid[x-1][y]].p(), ns[u].p(), oo);
if(Mid[x][y-1]) sol.AddEdge(ns[Mid[x][y-1]].p(), ns[u].p(), oo);
if(Mid[x+1][y+1]) sol.AddEdge(ns[Mid[x+1][y+1]].p(), ns[u].p(), oo);
return ;
}
void add_black(int x, int y) {
if(0 <= x && x < maxx && 0 <= y && y < maxx) ;
else return ;
add(black, x + 1, y);
add(black, x, y + 1);
add(black, x - 1, y - 1);
int u = Mid[x][y];
if(Mid[x+1][y]) sol.AddEdge(n2[u].p(), ns[Mid[x+1][y]].p(), oo);
if(Mid[x][y+1]) sol.AddEdge(n2[u].p(), ns[Mid[x][y+1]].p(), oo);
if(Mid[x-1][y-1]) sol.AddEdge(n2[u].p(), ns[Mid[x-1][y-1]].p(), oo);
return ;
}
#define vit vector <int> :: iterator
int main() {
int n = read(); sol.init();
int sum = 0;
for(int i = 1; i <= n; i++) {
int x = read(), y = read(), z = read(), v = read();
x -= z; y -= z;
x += 2000; y += 2000;
Map[x][y] += v;
}
for(int x = 0, i = 0; x < maxx; x++)
for(int y = 0; y < maxx; y++) if(Map[x][y]) {
int v = Map[x][y]; Mid[x][y] = ++i;
ns[i] = Node(x, y, (x + y - 4000) % 3 ? v * 10 : v * 11);
sum += ns[i].val;
if((x + y - 4000) % 3 == 0) middle.push_back(i);
}
for(vit i = middle.begin(); i != middle.end(); i++) {
int x = ns[*i].x, y = ns[*i].y;
sol.AddEdge(ns[*i].p(), n2[*i].p(), ns[*i].val);
add_white(x, y);
add_black(x, y);
}
sort(white.begin(), white.end());
vit it = unique(white.begin(), white.end());
for(vit i = white.begin(); i != it; i++) sol.AddEdge(Source.p(), ns[*i].p(), ns[*i].val);
sort(black.begin(), black.end());
it = unique(black.begin(), black.end());
for(vit i = black.begin(); i != it; i++) sol.AddEdge(ns[*i].p(), Tank.p(), ns[*i].val);
sol.setn(Cnt);
printf("%.1lf
", (sum - sol.MaxFlow(Source.p(), Tank.p())) / 10.0);
return 0;
}
Dinic 里面 BFS() 中如果忘了 vis[s] = 1 这句话会 T。。。