题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2879
数据生成器：http://paste.ubuntu.com/23196968/
官方数据：http://pan.baidu.com/s/1nv4ginB
这题就是修车的升级版
除了动态加点，别无其他神奇的玩意儿
接下来请欣赏《论S与T的区别》：
看起来厨师拆开的点连到T，与连到S没什么区别
然而…….
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 100+9;
const int N = 1000+9;
const int M = N*100;
const int INF = 100000000;
int n,m,head[N],nxt[M],to[M],cost[M],dis[N],flow[M];
int inq[N],cnt,cur[N],mat[L][L],id[N],vout,S,T,sur[N];
queue<int> que;
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 void Add_Edge(int u, int v, int f, int c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
inline bool SPFA() {
memset(dis,127,sizeof(dis));
que.push(S); inq[S] = 1; dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
}
} return dis[T] < 1000000000;
}
inline void MCMF(){
for (int nw;SPFA();) {
for (int w=T;w!=S;w=to[sur[w]^1]) nw = id[w]?id[w]:nw, flow[sur[w]]--, flow[sur[w]^1]++;
id[++cnt] = nw; cur[nw]++; Add_Edge(S,cnt,1,0); vout += dis[T];
for (int j=1;j<=n;j++) Add_Edge(cnt,j,1,mat[j][nw]*cur[nw]);
}
}
int main(){
n = read(); m = read(); S = 0; T = N - 1; cnt = n+m;
for (int i=1,tmp;i<=n;i++) Add_Edge(i,T,tmp=read(),0);
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) mat[i][j] = read();
for (int i=1;i<=m;i++) {
id[i+n] = i; cur[i] = 1; Add_Edge(S,i+n,1,0);
for (int j=1;j<=n;j++) Add_Edge(i+n,j,1,mat[j][i]);
} MCMF(); printf("%d\n",vout);
return 0;
}
I’ve learn several excellent stuff here. Definitely price bookmarking for
revisiting. I wonder how so much attempt you set to create such a great informative
web site.
Oh my goodness! Amazing article dude! Many thanks, However I am having issues
with your RSS. I don’t understand the reason why I am unable to join it.
Is there anybody having similar RSS problems? Anyone that knows the solution will you kindly
respond? Thanks!!
I would like to thank you for the efforts you’ve put in penning this blog.
I am hoping to see the same high-grade blog posts by you later on as well.
In truth, your creative writing abilities has encouraged me to get my
own website now 😉
This is my first time visit at here and i am in fact happy to read all at single
place.
I’m gone to convey my little brother, that he should also pay a visit this web site on regular basis to obtain updated from hottest news.
Hello there! I could have sworn I’ve visited
this web site before but after going through some of the posts I
realized it’s new to me. Regardless, I’m certainly pleased I
found it and I’ll be book-marking it and checking back often!
Hi there, I do think your site may be having internet browser compatibility
problems. When I take a look at your blog in Safari, it looks fine but when opening in Internet Explorer, it’s got some overlapping
issues. I just wanted to give you a quick heads up!
Besides that, excellent blog!
Magnificent goods from you, man. I have have in mind your stuff prior to
and you’re just too fantastic. I actually like what you
have obtained here, certainly like what you are saying and the best
way wherein you are saying it. You’re making it entertaining and you still care for to stay it
smart. I cant wait to read much more from you.
This is really a terrific web site.
Ahaa, its pleasant discussion on the topic of this post here at
this website, I have read all that, so now me also commenting here.
This paragraph provides clear idea in favor of the new viewers of blogging,
that genuinely how to do blogging and site-building.
Hi there excellent website! Does running a blog similar to this require a massive amount work?
I have virtually no knowledge of coding however I was hoping
to start my own blog soon. Anyway, if you have any ideas or techniques
for new blog owners please share. I know this is off subject
nevertheless I simply wanted to ask. Cheers!
Fastidious response in return of this question with solid arguments and describing all on the topic of
that.
Wow! This blog looks just like my old one! It’s
on a completely different subject but it has pretty much the same page layout and design. Wonderful
choice of colors!
Howdy would you mind stating which blog platform you’re
using? I’m planning to start my own blog soon but I’m having a difficult time
making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs and
I’m looking for something unique. P.S My apologies for being off-topic but I had to
ask!
Great post.
Ahaa, its fastidious conversation concerning this paragraph at this place
at this web site, I have read all that, so at
this time me also commenting at this place.
Hi there friends, its great piece of writing on the topic of teachingand completely explained, keep it up all the time.
I am in fact glad to read this web site posts which includes lots of helpful data, thanks for providing such statistics.
Hello There. I found your blog using msn. This is an extremely
well written article. I’ll make sure to bookmark
it and return to read more of your useful info. Thanks for
the post. I will certainly comeback.
I think this is among the most important info for me. And i’m glad reading your article.
But want to remark on few general things, The website style is great,
the articles is really excellent : D. Good job, cheers
Hello, I enjoy reading all of your article.
I wanted to write a little comment to support you.
natalielise plenty of fish
It’s nearly impossible to find experienced people for this topic, however,
you sound like you know what you’re talking about! Thanks
There is certainly a lot to know about this topic. I love all the points you’ve
made.
Very nice article, totally what I needed.
Yesterday, while I was at work, my cousin stole my apple ipad and tested to see if it can survive a
25 foot drop, just so she can be a youtube sensation. My apple ipad
is now broken and she has 83 views. I know this is totally off topic but I had to share it with someone!
I’m curious to find out what blog system you’re
working with? I’m experiencing some minor security problems with my latest blog and I’d like to find something more secure.
Do you have any solutions?
Greate article. Keep writing such kind of info on your blog.
Im really impressed by it.
Hello there, You’ve done a fantastic job. I’ll definitely digg it and in my opinion suggest
to my friends. I’m sure they will be benefited from
this site.
What’s up it’s me, I am also visiting this web page on a regular basis, this site is really fastidious and the viewers are in fact
sharing nice thoughts.
I do not even understand how I ended up right here,
but I believed this post used to be great. I don’t recognise who you might be however certainly you’re going to
a well-known blogger when you are not already.
Cheers!
Heya i am for the first time here. I found this board and I find
It truly useful & it helped me out a lot. I hope to give something back and aid others like you aided me.
With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement?
My website has a lot of completely unique content I’ve either created myself
or outsourced but it looks like a lot of it is popping it up all over the internet
without my authorization. Do you know any methods to help reduce content from being
stolen? I’d definitely appreciate it.
When some one searches for his vital thing, so he/she desires to be available that in detail,
thus that thing is maintained over here.
Informative article, totally what I wanted to find.
I have to thank you for the efforts you have put
in penning this website. I am hoping to see the same high-grade content from you in the future as well.
In truth, your creative writing abilities has encouraged me to get my very own site now 😉
Its such as you read my thoughts! You appear to understand so much approximately this, such as you wrote
the book in it or something. I feel that you simply could
do with some p.c. to pressure the message home a little bit,
but instead of that, that is fantastic blog. A fantastic read.
I’ll certainly be back.
I like the valuable info you provide in your articles. I will bookmark your blog and check
again here regularly. I am quite certain I will learn lots of
new stuff right here! Good luck for the next!
This article will assist the internet users for setting up new
weblog or even a blog from start to end.
I must thank you for the efforts you’ve put in writing this website.
I really hope to see the same high-grade content by you in the future
as well. In truth, your creative writing abilities has inspired me
to get my very own blog now 😉
Hi just wanted to give you a brief heads up and let you know a few of the images
aren’t loading properly. I’m not sure why but I think its a
linking issue. I’ve tried it in two different internet browsers and both show the same outcome.
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 completely off topic but I had to tell someone!
I’m no longer certain the place you are getting your information,
but good topic. I needs to spend some time studying much
more or working out more. Thanks for wonderful information I used to be on the lookout for
this information for my mission.
Hello there, I discovered your blog by means of
Google whilst looking for a comparable matter, your
site came up, it seems to be great. I have bookmarked it in my google bookmarks.
Hi there, simply became alert to your weblog
via Google, and found that it is really informative. I am gonna
be careful for brussels. I’ll appreciate when you proceed this in future.
Many other people shall be benefited from your writing. Cheers!
Hi there, for all time i used to check blog posts here in the early hours in the
dawn, because i love to gain knowledge of more and more.
Hi there! This post couldn’t be written any better!
Reading through this post reminds me of my previous room mate!
He always kept talking about this. I will forward this post to him.
Fairly certain he will have a good read. Thanks for
sharing!
Yes! Finally someone writes about plenty of fish dating
site.
I have been browsing online more than three hours these days, but I by no means discovered any interesting article like yours.
It’s lovely price enough for me. In my opinion, if all site owners and bloggers made just right content as you did, the web will be
much more helpful than ever before.
If some one wishes to be updated with hottest technologies then he must be
visit this site and be up to date all the time.
Definitely believe that which you said. Your favorite justification appeared to
be on the net the simplest thing to be aware of. I say to
you, I definitely get annoyed while people consider worries that they just don’t
know about. You managed to hit the nail upon the top and also defined out the whole thing without having side
effect , people could take a signal. Will probably be back to get more.
Thanks
These are actually great ideas in regarding blogging.
You have touched some good points here. Any way keep up wrinting.
Having read this I thought it was very informative.
I appreciate you spending some time and effort to put this short article together.
I once again find myself spending way too much time
both reading and leaving comments. But so what, it was still worthwhile!
Superb post but I was wanting to know if you could write
a litte more on this subject? I’d be very thankful if you could elaborate a
little bit more. Bless you!
Hello! Do you know if they make any plugins to assist with SEO?
I’m trying to get my blog to rank for some targeted keywords but
I’m not seeing very good success. If you know of any please share.
Appreciate it!
Greate post. Keep writing such kind of info on your page. Im really impressed by your site.
Hi there, You have performed a fantastic job.
I’ll definitely digg it and personally suggest to my friends.
I am confident they will be benefited from this site.
I like the valuable information you provide in your articles.
I’ll bookmark your weblog and check again here
frequently. I am quite sure I’ll learn many new stuff right here!
Best of luck for the next!
I’m not sure where you’re getting your information, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for great information I was looking for this
info for my mission.
Everything posted made a ton of sense. However, think about this, what if you wrote a catchier
title? I ain’t suggesting your information isn’t solid,
but what if you added a post title to maybe grab folk’s attention?
I mean 【BZOJ 2879】[Noi2012] 美食节 – Qizy'
s Database is kinda plain. You could peek at Yahoo’s home page and watch how they create article headlines
to grab people interested. You might try adding
a video or a picture or two to get people interested about what you’ve
written. Just my opinion, it could make your blog a little bit more interesting.
I have been browsing online more than 3 hours nowadays, but I
never discovered any interesting article like yours. It is lovely price enough for
me. Personally, if all site owners and bloggers
made excellent content material as you probably did, the internet
shall be much more useful than ever before.
Hey there I am so delighted I found your site, I really found you
by accident, while I was looking on Aol for something else, Nonetheless I am here now and would just like to say thank you for
a fantastic post and a all round entertaining blog (I also love
the theme/design), I don’t have time to read through it all at the minute but
I have saved it and also added your RSS feeds, so when I have time I
will be back to read much more, Please do keep up the great work.
Woah! I’m really digging the template/theme of this site.
It’s simple, yet effective. A lot of times it’s challenging
to get that “perfect balance” between usability and appearance.
I must say you have done a very good job with this.
Also, the blog loads very fast for me on Opera. Exceptional Blog!
Appreciate the recommendation. Will try it out.
I really love your website.. Very nice colors & theme.
Did you create this website yourself? Please reply back as I’m
wanting to create my own personal website and would love to
learn where you got this from or just what the theme is called.
Kudos!
Hello, i think that i saw you visited my web site thus i came to “return the favor”.I am trying to
find things to improve my web site!I suppose its ok to
use some of your ideas!!
I’ve been exploring for a little for any high quality
articles or blog posts on this kind of house . Exploring
in Yahoo I finally stumbled upon this site. Studying this info So i’m satisfied
to show that I’ve an incredibly just right uncanny feeling I came upon exactly what I needed.
I most unquestionably will make sure to do not forget this website and give it a glance
on a relentless basis.
You’re so awesome! I do not think I have read through something like that
before. So great to find another person with a few original
thoughts on this issue. Really.. thanks for starting this up.
This website is one thing that is required on the internet,
someone with a little originality!
It’s awesome to pay a quick visit this web page and reading
the views of all friends concerning this piece of writing, while
I am also keen of getting knowledge.
Spot on with this write-up, I seriously think this website needs a great deal more attention.
I’ll probably be back again to see more, thanks
for the information!
Your way of telling the whole thing in this piece of writing is truly fastidious, all
be able to simply be aware of it, Thanks a lot.
Hello my family member! I want to say that this post is awesome, great written and include
almost all vital infos. I would like to peer more posts like this .
Hello there! This blog post could not be written any better!
Going through this post reminds me of my previous roommate!
He constantly kept preaching about this. I’ll send this information to him.
Fairly certain he will have a great read. Many thanks for sharing!
With havin so much written content do you ever run into any issues of plagorism or copyright violation? My site has a lot of completely unique content I’ve either authored myself or outsourced but it appears a lot of it is popping it up all over the web without my permission. Do you know any solutions to help stop content from being stolen? I’d certainly appreciate it.
You should be a part of a contest for one of the best blogs on the web.
I will highly recommend this web site!
You really make it seem so easy with your presentation but I find this matter to be actually something
that I think I would never understand. It seems
too complex and very broad for me. I’m looking forward for your next post, I’ll
try to get the hang of it!
Please let me know if you’re looking for a writer for your site.
You have some really great posts and I feel I would be
a good asset. If you ever want to take some of the
load off, I’d absolutely love to write some material for your
blog in exchange for a link back to mine. Please shoot me
an email if interested. Cheers!
I have been exploring for a little for any high quality articles or weblog posts on this kind of house
. Exploring in Yahoo I finally stumbled upon this web site.
Studying this info So i’m happy to convey that I have an incredibly excellent uncanny feeling I discovered just what I needed.
I such a lot undoubtedly will make sure to don?t fail to remember this website and
give it a look regularly.
This blog was… how do I say it? Relevant!! Finally I’ve found something which helped me.
Thanks a lot!
If you are going for finest contents like myself, only pay a visit this
site everyday as it presents feature contents, thanks
Ahaa, its nice discussion concerning this article at this place at this web site,
I have read all that, so at this time me also commenting at this place.
What’s up everyone, it’s my first go to see at this web page, and post is
in fact fruitful in favor of me, keep up posting
these types of posts.
Hey there! I just want to give you a big thumbs up for the great
information you have right here on this post.
I’ll be returning to your web site for more soon.
An interesting discussion is definitely worth comment. I think that you should write more about this
topic, it might not be a taboo matter but usually people don’t speak about such subjects.
To the next! All the best!!
When I originally left a comment I seem to have clicked the -Notify me when new comments are added- checkbox and from now on every time a comment is added I recieve 4
emails with the same comment. There has to be a means you are able
to remove me from that service? Cheers!
Oh my goodness! Amazing article dude! Thank you so much, However I am having troubles with your RSS.
I don’t understand why I cannot subscribe to it. Is there anybody getting the same
RSS problems? Anybody who knows the solution will you kindly respond?
Thanx!!
Hello it’s me, I am also visiting this website daily,
this website is in fact good and the viewers are
really sharing nice thoughts.
Incredible story there. What happened after? Thanks!
I believe this is among the so much vital information for me.
And i am happy studying your article. But should remark on few normal issues, The website taste
is perfect, the articles is really excellent : D. Excellent process, cheers
Hey there! Do you use Twitter? I’d like to follow you if that would be okay.
I’m undoubtedly enjoying your blog and look forward to new updates.
No matter if some one searches for his essential thing, therefore he/she needs to be available that in detail, thus that
thing is maintained over here.
You are so awesome! I don’t suppose I’ve read anything like this
before. So nice to discover another person with a
few genuine thoughts on this subject matter. Seriously..
thanks for starting this up. This site is something that is required on the internet, someone with some originality!
Hmm it looks like your site ate my first comment (it was super long) so
I guess I’ll just sum it up what I wrote and say,
I’m thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new to the
whole thing. Do you have any suggestions for inexperienced blog writers?
I’d definitely appreciate it.
I like it whenever people get together and share thoughts.
Great site, keep it up!
My programmer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using WordPress on numerous websites for
about a year and am anxious about switching to another platform.
I have heard good things about blogengine.net. Is there a way I can transfer all my wordpress posts into it?
Any help would be really appreciated!
This website was… how do I say it? Relevant!!
Finally I’ve found something which helped me. Many thanks!
Definitely believe that which you said. Your favorite
reason 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 don’t know about.
You managed to hit the nail upon the top as well as defined out the whole thing without
having side effect , people could take a signal. Will probably be back to get more.
Thanks
I was very happy to find this web site. I need to to thank you for
ones time just for this fantastic read!! I definitely enjoyed every part of it and i
also have you book-marked to look at new things in your website.
What’s up to all, the contents existing at this site are in fact amazing
for people knowledge, well, keep up the nice work fellows.
Fantastic beat ! I wish to apprentice while you
amend your web site, how can i subscribe
for a blog web site? The account aided me a acceptable
deal. I had been a little bit acquainted of this your broadcast provided bright clear concept
Wonderful work! This is the type of information that should be shared around the internet. Shame on the search engines for not positioning this post higher! Come on over and visit my web site . Thanks =)
I need help and ideas to start a new website?
Really informative article post.Really looking forward to read more.
Really informative blog article. Fantastic.
How do I start and use a blog? Also, what is the best blogging site?