题目传送门：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
Howdy would you mind stating which blog platform you’re using?
I’m looking to start my own blog soon but I’m having
a difficult time deciding between BlogEngine/Wordpress/B2evolution and
Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
P.S Sorry for getting off-topic but I had to ask!
What’s up, the whole thing is going sound here and ofcourse every one is sharing information, that’s genuinely fine, keep up writing.
Ahaa, its good dialogue regarding this piece of writing here at this website,
I have read all that, so now me also commenting here.
Hi! I know this is kinda off topic but I was wondering which blog
platform are you using for this website? I’m getting sick and tired
of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the direction of a good platform.
Have you ever considered about adding a little bit more than just your articles?
I mean, what you say is valuable and everything. But think about if you added
some great pictures or videos to give your posts more, “pop”!
Your content is excellent but with pics and videos,
this website could certainly be one of the best in its field.
Excellent blog!
Keep on working, great job!
Wonderful article! We are linking to this great article on our website.
Keep up the great writing.
Sweet blog! I found it while browsing on Yahoo News.
Do you have any suggestions on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Cheers
You can definitely see your enthusiasm in the article you write.
The sector hopes for even more passionate writers such as
you who are not afraid to say how they believe. At all
times go after your heart.
I got this site from my pal who told me about this web site and now this time I am browsing this site and reading very
informative articles at this time.
Because the admin of this web site is working, no hesitation very quickly it will be famous, due to
its quality contents.
Hey there! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything
I’ve worked hard on. Any recommendations?
Hi, i read your blog occasionally and i own a similar one and
i was just wondering if you get a lot of spam comments?
If so how do you protect against it, any plugin or anything you can advise?
I get so much lately it’s driving me crazy so any help is very much
appreciated.
of course like your web-site but you have to take a look at the spelling on several of your posts.
A number of them are rife with spelling problems
and I to find it very bothersome to inform the truth then again I’ll definitely come again again.
You’ve made some really good points there. I looked on the net for
additional information about the issue and found most
individuals will go along with your views on this web site.
I am now not certain the place you’re getting your information, however great topic.
I needs to spend a while learning more or working out more.
Thank you for fantastic info I was looking for this information for my mission. plenty of fish natalielise
Hi! I’ve been reading your website for a while now and
finally got the bravery to go ahead and give you a shout out from
Houston Tx! Just wanted to tell you keep up the great
job!
Hi, Neat post. There is an issue along with your web site in internet explorer, would
check this? IE still is the marketplace chief and a good part
of people will omit your wonderful writing due to this problem.
Informative article, exactly what I was looking
for. natalielise pof
Thanks for sharing your thoughts. I really appreciate your efforts and I
will be waiting for your next write ups thank you once again.
Thank you for every other great article. Where else may anyone
get that kind of information in such a perfect means of
writing? I’ve a presentation subsequent week, and I am on the search for such info.
Keep on writing, great job!
Good site you have here.. It’s difficult to find excellent writing like yours nowadays.
I seriously appreciate people like you! Take
care!!
Undeniably believe that which you stated. Your favorite justification appeared to be on the
net the easiest thing to be aware of. I say to
you, I definitely get annoyed while people consider worries that they plainly do not
know about. You managed to hit the nail upon the top and defined out the whole thing without having side effect , people can take a
signal. Will likely be back to get more. Thanks
Hey very nice blog!
I’m no longer positive the place you are getting
your information, but great topic. I must spend a while studying much more or working out more.
Thank you for magnificent information I was on the lookout for this info for my mission.
I am in fact thankful to the holder of this web page who has shared this fantastic article
at at this time.
Hey There. I discovered your weblog using msn. This
is a really well written article. I’ll make sure to bookmark it and come back to read
extra of your useful info. Thank you for the post.
I will certainly comeback.
This is really interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more of your excellent post.
Also, I’ve shared your web site in my social
networks!
Hmm is anyone else experiencing problems with the images on this blog loading?
I’m trying to find out if its a problem on my end or
if it’s the blog. Any feed-back would be greatly appreciated.
Actually when someone doesn’t know then its up to other viewers that
they will help, so here it occurs.
Hi just wanted to give you a quick heads up and let
you know a few of the images aren’t loading correctly. I’m not sure why but
I think its a linking issue. I’ve tried it in two different web browsers and both show the same outcome.
My brother recommended I may like this blog. He used to be entirely right.
This submit actually made my day. You can not believe just how so much time I had
spent for this information! Thanks!
whoah this weblog is great i like reading your articles.
Keep up the great work! You know, lots of persons are looking round for this information, you can aid
them greatly.
Thanks for finally writing about >【BZOJ 4625】[BeiJing2016] 水晶 – Qizy’s Database
<Liked it!
That is a really good tip especially to those new to the blogosphere.
Simple but very precise information… Thank you for sharing this one.
A must read post!
My brother recommended I would possibly like this blog.
He was totally right. This publish actually
made my day. You can not believe simply how so much
time I had spent for this info! Thank you!
You have made some decent points there. I checked on the web for more info about the issue and found most individuals will go along with your views
on this web site.
Magnificent beat ! I wish to apprentice while you amend your site,
how could i subscribe for a weblog site? The account aided me a applicable deal.
I had been tiny bit acquainted of this your broadcast provided vibrant transparent idea
Thankfulness to my father who shared with me on the topic of
this web site, this web site is actually awesome.
Hi there to every body, it’s my first pay a quick
visit of this webpage; this webpage consists of remarkable and actually fine stuff
in support of visitors.
Hi there, I enjoy reading through your article.
I wanted to write a little comment to support you.
Hi there, just wanted to mention, I loved this post.
It was helpful. Keep on posting!
Way cool! Some extremely valid points! I appreciate you
penning this post plus the rest of the site is also very good.
I go to see every day a few sites and sites to read articles, but this webpage presents
quality based posts.
Today, I went to the beach with my children. I found a sea shell and gave it
to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is entirely off topic but I had to tell
someone!
Great, thanks for sharing this blog.Thanks Again. Much obliged.
I have read several just right stuff here. Definitely worth bookmarking for revisiting.
I surprise how a lot effort you place to create such a great informative site.
Hi colleagues, good piece of writing and nice arguments commented here, I am truly enjoying by these.
Thanks for finally talking about >【BZOJ 4625】[BeiJing2016] 水晶 – Qizy’s Database <Loved it!
whoah this blog is wonderful i really like studying your posts.
Keep up the good work! You already know, lots of persons are
searching round for this information, you can help them greatly.
Thanks to my father who informed me concerning this weblog, this blog is actually amazing.
Hi, I think your website might be having browser compatibility issues.
When I look at your blog site in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, great blog!
Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said
“You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear. She
never wants to go back! LoL I know this is entirely off topic but I had to tell someone!
I think everything said was actually very logical.
However, consider this, what if you composed a catchier post title?
I mean, I don’t wish to tell you how to run your blog, however
suppose you added something that grabbed people’s attention? I mean 【BZOJ 4625】[BeiJing2016] 水晶 – Qizy'
s Database is kinda vanilla. You could glance at Yahoo’s front page and watch how
they write news titles to grab viewers to click. You
might try adding a video or a picture or two to get
people excited about everything’ve written. In my opinion, it could make your
blog a little livelier.
What’s up, for all time i used to check web site posts
here early in the daylight, since i enjoy to find out more and more.
Really no matter if someone doesn’t be aware of then its up
to other visitors that they will help, so here it happens.
I will right away grasp your rss as I can’t find your e-mail
subscription hyperlink or e-newsletter service. Do you have any?
Kindly let me know so that I may just subscribe. Thanks.
It’s going to be end of mine day, however before ending I
am reading this fantastic paragraph to increase my knowledge.
I think this is one of the most important info for me. And
i am glad reading your article. But wanna remark on some general things, The web site style is ideal, the articles is really great :
D. Good job, cheers
Hi! I realize this is kind of off-topic however I had to ask.
Does running a well-established website like yours take a large
amount of work? I am completely new to running a blog but I do write in my diary
everyday. I’d like to start a blog so I can easily share
my own experience and views online. Please let me know if you have any kind of recommendations or tips for brand new
aspiring bloggers. Thankyou!
I am in fact happy to read this weblog posts which contains plenty of
valuable data, thanks for providing these statistics.
Whoa! This blog looks exactly like my old one! It’s on a completely different subject
but it has pretty much the same layout and design.
Excellent choice of colors!
I constantly spent my half an hour to read this weblog’s
articles everyday along with a mug of coffee.
Fine way of telling, and pleasant paragraph to get facts regarding my presentation focus, which i am going to present in school.
Sweet blog! I found it while surfing around on Yahoo News. Do you have
any suggestions on how to get listed in Yahoo
News? I’ve been trying for a while but I never seem to get there!
Many thanks
Very soon this website will be famous among all blogging people, due to it’s
fastidious content
Great weblog here! Additionally your website a lot up very fast!
What host are you the use of? Can I get your associate
hyperlink to your host? I want my site loaded up
as fast as yours lol
I’m really enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire
out a designer to create your theme? Superb work!
Pretty nice post. I simply stumbled upon your blog and wished to
say that I have really loved surfing around your weblog posts.
After all I’ll be subscribing to your feed and I am hoping you write once more very soon!
First of all I would like to say superb blog!
I had a quick question in which I’d like to ask if you don’t mind.
I was interested to find out how you center yourself and clear your
thoughts before writing. I have had a tough time clearing my thoughts in getting my thoughts
out there. I truly do take pleasure in writing however it just seems like the first 10 to 15 minutes are generally wasted just trying
to figure out how to begin. Any recommendations or
hints? Kudos!
What’s up, just wanted to tell you, I enjoyed this post.
It was helpful. Keep on posting!