题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4625
数据生成器：http://paste.ubuntu.com/23154162/
这个题目网上为什么搜不到题解QAQ
那我就来撸一份题解吧 =￣ω￣=
我们将六边形按照 (x+y+z)%3 == 0/1/2 来分类（染色）
不难发现，会变成这个样子：
之后，我们发现：两种共振一定是三个不同颜色的点产生的
于是把两种共振合起来考虑
因为我们必须任意三个中至少删一个，于是考虑最小割模型
将%3=1的点和S连一起，%3=2的和T连一起，%3=0的拆成两个点
现在产生共振的话，就连在一起。
这样的话，刚好符合题目的要求，于是跑一跑Dinic即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500000+9;
const int M = 1000000+9;
const int SGZ = 4100+9;
const int INF = 100000000;
int n,mat[SGZ][SGZ],idx[SGZ][SGZ],S,T,vout;
int nxt[M],head[N],to[M],flow[M],dis[N],cur[N];
struct Point{int x,y,t,c;}p[N];
queue<int> que;
inline bool cmp(const Point &A, const Point &B) {return A.x == B.x && A.y == B.y;}
inline bool CMP(const Point &A, const Point &B) {return A.x < B.x || (A.x == B.x && A.y < B.y);}
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
}
return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f,flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
return ret;
}
}
inline int Dinic(){
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
} return ret;
}
inline void Add_Edge(int u, int v, int f){
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = f;
to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = 0;
}
int main(){
n = read();
for (int i=1,x,y,z,c;i<=n;i++) {
x = read(); y = read(); z = read(); c = read();
x += 2001 - z; y += 2001 - z; p[i].t = (x+y) % 3;
c *= ((x+y)%3)?10:11; mat[x][y] += c; vout += c;
p[i].x = x; p[i].y = y;
}
sort(p+1,p+1+n,CMP);
n = unique(p+1,p+1+n,cmp) - p - 1;
S = n*2 + 1, T = n*2 + 2;
for (int i=1;i<=n;i++) idx[p[i].x][p[i].y] = i, p[i].c = mat[p[i].x][p[i].y];
for (int i=1;i<=n;i++)
if (p[i].t == 1) Add_Edge(S,i,p[i].c);
else if (p[i].t == 2) Add_Edge(i,T,p[i].c);
else Add_Edge(i,i+n,p[i].c);
for (int i=1,x,y;i<=n;i++) if (!p[i].t) {
x = p[i].x; y = p[i].y;
if (idx[x+1][y]) Add_Edge(idx[x+1][y],i,INF);
if (idx[x][y+1]) Add_Edge(idx[x][y+1],i,INF);
if (idx[x-1][y-1]) Add_Edge(idx[x-1][y-1],i,INF);
if (idx[x+1][y+1]) Add_Edge(i+n,idx[x+1][y+1],INF);
if (idx[x][y-1]) Add_Edge(i+n,idx[x][y-1],INF);
if (idx[x-1][y]) Add_Edge(i+n,idx[x-1][y],INF);
}
vout -= Dinic();
cout<<vout/10<<'.'<<vout%10;
return 0;
}
至于怎样如何很自然地想到这样构图
我也不知道
已经问了YYY，但他还没有回我QAQ
—– UPD 2016.9.10 —–
YYY告诉我，这货不是很常见的构图？
来源于多米诺骨牌模型？
—– UPD 2016.9.13 —–
刚好看到YYY提到的那一类题目了
http://acm.hit.edu.cn/hoj/problem/view?id=2713