题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3345
这题就是一个全局最小割，其中分治最小割的做法肯定是正确的
于是水之，1.4s卡过
全局最小割专门的算法还是很优越的样子
无论是时间复杂度或是编程复杂度
但我这个蒟蒻学不会QAQ
弃坑
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;
int head[N],nxt[M],to[M],flow[M],cur[N];
int n,m,vout=INF,cnt,id[N],dis[N],pur,T=1;
queue<int> que;
inline void Add_Edge(int u, int v, int w) {
to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}
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(int s, int t) {
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 == pur) 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;
ret += tmp; f -= tmp; if (!f) return ret;
}
return ret;
}
}
inline int Dinic(int s, int t){
int ret = 0; pur = t;
while (BFS(s,t)) {
memcpy(cur,head,sizeof(head));
ret += DFS(s,INF);
} return ret;
}
void SIGN(int w) {
dis[w] = 1;
for (int i=head[w];i;i=nxt[i])
if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}
void solve(int l , int r){
if (l >= r) return ;
static int tmp[N]; int L=l-1, R=r+1;
for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
vout = min(vout, Dinic(id[l],id[r]));
memset(dis,-1,sizeof(dis)); SIGN(id[l]);
for (int i=l;i<=r;i++)
if (~dis[id[i]]) tmp[++L] = id[i];
else tmp[--R] = id[i];
for (int i=l;i<=r;i++) id[i] = tmp[i];
solve(l,L); solve(R,r);
}
int main(){
n = read(); m = read();
for (int i=1,u,v,w;i<=m;i++) u = read(), v = read(), w = read(), Add_Edge(u,v,w);
for (int i=1;i<=n;i++) id[i] = i; solve(1,n);
printf("%d\n",vout);
return 0;
}
Have you ever thought about adding a little bit more than just your articles?
I mean, what you say is important and everything.
However just imagine if you added some great images or videos
to give your posts more, “pop”! Your content is excellent but
with images and video clips, this blog could certainly be one of the very best in its niche.
Fantastic blog!
Undeniably imagine that that you stated. Your favourite reason seemed to be
on the internet the simplest thing to be aware of.
I say to you, I definitely get irked whilst other people consider worries that
they plainly don’t understand about. You controlled to hit the nail upon the top and defined
out the whole thing with no need side effect , people can take a signal.
Will likely be back to get more. Thanks
Having read this I thought it was really enlightening. I appreciate you finding the time and effort to put this information together.
I once again find myself personally spending a lot of time
both reading and posting comments. But so what,
it was still worthwhile!
It’s a shame you don’t have a donate button! I’d certainly donate
to this brilliant blog! I guess for now i’ll settle for
book-marking and adding your RSS feed to my Google
account. I look forward to brand new updates and will talk about this website with my Facebook group.
Chat soon!
Thanks for your marvelous posting! I certainly enjoyed reading it,
you are a great author. I will be sure to bookmark your blog and will eventually come back later in life.
I want to encourage you to continue your great posts, have
a nice evening!
It’s enormous that you are getting thoughts from this
paragraph as well as from our argument made at this place.
I’m not sure why but this site is loading very slow for me.
Is anyone else having this problem or is it a problem on my end?
I’ll check back later and see if the problem still exists.
If some one needs to be updated with newest technologies after that he must be pay a quick visit this web
site and be up to date all the time.
you’re actually a good webmaster. The web site loading pace is amazing.
It seems that you’re doing any unique trick. In addition, The contents are masterwork.
you’ve performed a magnificent activity in this subject!
Article writing is also a fun, if you be acquainted
with then you can write if not it is complicated
to write.
Hi there! This blog post couldn’t be written much better! Looking through this article reminds me of my previous
roommate! He continually kept talking about this. I will send this information to him.
Fairly certain he’s going to have a very good read. Thanks for sharing!
I am really impressed with your writing skills as well as with the layout on your weblog.
Is this a paid theme or did you modify it yourself? Anyway keep up the nice quality writing,
it is rare to see a nice blog like this one nowadays.
Fastidious answers in return of this matter with solid arguments and explaining everything on the topic of that.
I would like to thank you for the efforts you’ve put in penning this website.
I am hoping to see the same high-grade blog posts from you in the
future as well. In truth, your creative writing abilities has inspired me to get my very own site now ;
)
Its such as you read my mind! You appear to understand
so much approximately this, like you wrote the book in it or something.
I believe that you just can do with some % to force the message house a bit, but instead of that, this is
excellent blog. A fantastic read. I will certainly be
back.
After looking into a handful of the articles on your web page, I honestly like your
technique of blogging. I book marked it to my bookmark webpage list and will be checking back soon. Take a look at my website
as well and let me know how you feel.
I like what you guys tend to be up too. This kind of
clever work and exposure! Keep up the awesome works guys I’ve added you guys to my own blogroll.
natalielise plenty of fish
Because the admin of this website is working, no doubt very rapidly it will be renowned, due to
its feature contents.
In fact when someone doesn’t understand afterward its up to other users that
they will assist, so here it occurs.
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to
my blog that automatically tweet my newest twitter
updates. I’ve been looking for a plug-in like this
for quite some time and was hoping maybe you would have some experience
with something like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
plenty of fish natalielise
Hi, i think that i saw you visited my website so i came
to “return the favor”.I am attempting to find things
to improve my site!I suppose its ok to use some of your ideas!!
Does your blog have a contact page? I’m having problems locating
it but, I’d like to send you an e-mail. I’ve got some
ideas for your blog you might be interested in hearing.
Either way, great website and I look forward to seeing it expand over time.
Simply desire to say your article is as amazing. The clarity for your put up is just cool and that i can assume you’re a professional on this
subject. Well along with your permission allow me to
grab your feed to stay up to date with imminent post.
Thank you 1,000,000 and please keep up the enjoyable work.
plenty of fish natalielise
Thanks for the good writeup. It in reality used to be a enjoyment account it.
Look complicated to far brought agreeable from you!
By the way, how can we keep up a correspondence?
plenty of fish natalielise
I love your blog.. very nice colors & theme. Did
you make this website yourself or did you hire someone to do it for you?
Plz respond as I’m looking to create my own blog and would like to know
where u got this from. thank you
What’s Going down i’m new to this, I stumbled upon this I’ve discovered It
positively useful and it has aided me out
loads. I am hoping to contribute & aid different customers
like its helped me. Great job.
Hi to all, the contents present at this site are actually
awesome for people knowledge, well, keep up the nice
work fellows.
This paragraph will assist the internet people for setting up new web site or
even a weblog from start to end.
Hey great website! Does running a blog similar to this
require a great deal of work? I have absolutely no understanding of computer programming however I had been hoping to start my own blog soon. Anyway,
if you have any suggestions or techniques for new blog owners
please share. I understand this is off subject however I just had to ask.
Appreciate it!
Hey! I could have sworn I’ve been to this site before but after browsing through some of the post I realized it’s new to me.
Anyhow, I’m definitely glad I found it and I’ll be book-marking and checking back often!
Awesome article.
Woah! I’m really enjoying the template/theme of this website.
It’s simple, yet effective. A lot of times it’s tough to get that “perfect balance” between usability and
appearance. I must say you have done a superb job with this.
Also, the blog loads extremely quick for me on Firefox.
Exceptional Blog!
I don’t know whether it’s just me or if perhaps everyone else encountering issues with your site.
It appears like some of the written text on your posts
are running off the screen. Can someone else please provide feedback and
let me know if this is happening to them as well? This could be a problem with my internet browser because I’ve had this happen previously.
Many thanks
I love your blog.. very nice colors & theme. Did you make this website
yourself or did you hire someone to do it for you? Plz answer back
as I’m looking to design my own blog and would like to find out where u got this from.
cheers
Paragraph writing is also a fun, if you be acquainted with then you
can write if not it is difficult to write.
Hi there just wanted to give you a quick heads up.
The words in your content seem to be running off the screen in Firefox.
I’m not sure if this is a formatting issue or something to do with browser compatibility but I thought I’d post
to let you know. The design look great though!
Hope you get the issue resolved soon. Thanks
Greetings! Quick question that’s totally off topic.
Do you know how to make your site mobile friendly?
My site looks weird when viewing from my iphone 4.
I’m trying to find a theme or plugin that might be able to correct this problem.
If you have any recommendations, please share. With thanks!
Its like you read my mind! You appear to understand
a lot approximately this, like you wrote the guide in it
or something. I feel that you simply can do with a few p.c.
to power the message house a bit, however other than that, this is fantastic blog.
A fantastic read. I’ll certainly be back.
It’s impressive that you are getting thoughts from this piece of writing as well as from our dialogue made here.
Hello there I am so happy I found your web site, I really found
you by error, while I was searching on Digg for something else, Anyhow I am here now and would
just like to say thanks a lot for a fantastic post and a all round interesting blog (I also love the theme/design), I don’t have time
to read it all at the moment but I have bookmarked it and also included your RSS feeds, so when I have time I will be back to read
much more, Please do keep up the superb work.
It’s going to be finish of mine day, however
before finish I am reading this enormous piece of writing to improve my experience.
I enjoy reading a post that can make men and women think.
Also, thanks for permitting me to comment!
Hey there would you mind letting me know which web host you’re using?
I’ve loaded your blog in 3 different web browsers and I must say this blog loads a
lot faster then most. Can you suggest a good web hosting provider at a reasonable price?
Kudos, I appreciate it!
Greetings! I know this is somewhat off topic but I
was wondering which blog platform are you using for this website?
I’m getting fed up of WordPress because I’ve had problems
with hackers and I’m looking at alternatives for another platform.
I would be fantastic if you could point me in the direction of a good platform.
Hi there this is kinda of off topic but I was wondering
if blogs use WYSIWYG editors or if you have to manually code
with HTML. I’m starting a blog soon but have no coding expertise so I wanted to
get guidance from someone with experience. Any help would be enormously
appreciated!
Valuable information. Lucky me I discovered your website
accidentally, and I’m stunned why this twist of fate did not happened in advance!
I bookmarked it.
Hello Dear, are you truly visiting this site daily,
if so after that you will absolutely take nice experience.
Wow! At last I got a blog from where I know how to truly take valuable information regarding my study and knowledge.
Magnificent items from you, man. I’ve consider your stuff previous to and you are simply extremely magnificent.
I really like what you have got right here, certainly like what you are saying and the best way in which you say it.
You are making it enjoyable and you continue to take care of to keep it smart.
I can’t wait to read much more from you. This is really a great website.
Thanks , I have just been searching for information about this topic for a while and yours is
the best I’ve discovered till now. However, what in regards to the
conclusion? Are you sure in regards to the
supply?
I have fun with, cause I discovered just what I used to be having a look for.
You have ended my four day long hunt! God Bless you man. Have a nice day.
Bye
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point.
You clearly know what youre talking about, why waste your intelligence on just posting videos to your
blog when you could be giving us something enlightening to
read?
Hi, just wanted to say, I enjoyed this blog post. It
was helpful. Keep on posting!
Excellent goods from you, man. I have understand your stuff previous
to and you are just extremely magnificent. I actually like what you’ve acquired here,
certainly like what you’re stating and the way in which you
say it. You make it entertaining and you still take care
of to keep it smart. I can’t wait to read much more from you.
This is really a wonderful web site.
Appreciating the hard work you put into your blog and in depth information you provide.
It’s great to come across a blog every once in a while that isn’t the same
outdated rehashed material. Fantastic read! I’ve saved your site and I’m adding your RSS feeds to my Google account.
It’s going to be ending of mine day, however before end I am reading this wonderful post to increase my
experience.
Pretty! This was an extremely wonderful post. Thanks for supplying this
information.
Hello, I enjoy reading all of your article. I
wanted to write a little comment to support you.
I was recommended this blog by way of my cousin.
I am not certain whether or not this submit is written by
means of him as no one else understand such specified about my difficulty.
You are amazing! Thank you!
Good day! This post could not be written any better!
Reading this post reminds me of my good old room mate! He always
kept talking about this. I will forward this post to him.
Pretty sure he will have a good read. Thanks for sharing!
I don’t even know how I finished up here, but I thought this publish used to be
great. I don’t understand who you are however definitely you are going to a famous
blogger if you happen to aren’t already. Cheers!
A fascinating discussion is worth comment. I think that you should write
more about this topic, it might not be a taboo matter but generally people don’t discuss these topics.
To the next! Cheers!!
This is really fascinating, You are an overly professional blogger.
I have joined your feed and stay up for in quest of more of your fantastic post.
Also, I have shared your website in my social networks
Hi! I know this is kind of off topic but I was wondering which
blog platform are you using for this site? I’m getting tired of WordPress because I’ve
had problems with hackers and I’m looking at options for another
platform. I would be great if you could point me
in the direction of a good platform.
My brother recommended I might like this web site.
He was totally right. This post actually made my
day. You cann’t imagine just how much time I had spent for this
information! Thanks!
Hey very interesting blog!
It’s hard to find experienced people for this topic,
but you sound like you know what you’re talking about! Thanks
It’s truly a nice and useful piece of info. I am glad that you just shared this helpful information with us. Please stay us up to date like this. Thanks for sharing.
Generally I don’t read post on blogs, but I would like to say that this
write-up very forced me to take a look at and do
so! Your writing style has been amazed me. Thanks, very great article.
Someone essentially lend a hand to make seriously articles
I’d state. This is the very first time I frequented your
web page and to this point? I surprised with the research you made to make this actual put up extraordinary.
Fantastic job!
I was suggested this web site by means of my cousin. I
am not certain whether or not this put up is written via him as
nobody else understand such exact about my difficulty.
You are amazing! Thanks!
I was suggested this web site by my cousin. I’m not sure whether this post is written by him as
nobody else know such detailed about my trouble.
You’re wonderful! Thanks!
What a information of un-ambiguity and preserveness of precious know-how about unpredicted feelings.
Its such as you learn my mind! You seem to grasp a lot approximately this,
such as you wrote the guide in it or something. I feel that you can do
with a few % to drive the message home a little bit,
but other than that, this is magnificent blog.
An excellent read. I’ll certainly be back.
Greetings from Carolina! I’m bored to death at work so I
decided to check out your website on my iphone during lunch break.
I enjoy the information you provide here and can’t wait to take a look when I get home.
I’m surprised at how quick your blog loaded on my mobile ..
I’m not even using WIFI, just 3G .. Anyhow, excellent site!
Thanks for finally writing about >【BZOJ 3345】[Pku2914] Minimum Cut –
Qizy’s Database <Loved it!
Good day very cool blog!! Guy .. Excellent ..
Wonderful .. I will bookmark your blog and take the feeds additionally?
I am glad to find so many helpful info here in the submit, we
want develop more strategies in this regard,
thanks for sharing. . . . . .
An outstanding share! I’ve just forwarded this onto
a coworker who was doing a little research on this.
And he actually ordered me lunch simply because I found it for him…
lol. So let me reword this…. Thanks for the meal!! But yeah, thanx
for spending some time to talk about this subject here on your web site.
I read this article completely concerning
the comparison of hottest and preceding technologies, it’s awesome article.
very nice submit, i certainly love this web site, carry on it
Im grateful for the article. Great.
I really enjoy the article.Much thanks again. Great.