题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1391
喜闻乐见大水题
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 10000;
const int M = 4000000;
const int INF = 1000000000;
int n,m,head[N],nxt[M],to[M],flow[M],dis[N],cur[N],S,T,vout;
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) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(S);
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]));
ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += 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;
}
int main(){
n = read(); m = read(); S = 0; T = N-1;
for (int i=1,t1,t2,t3;i<=n;i++) {
t1 = read(); Add_Edge(S,i,t1); vout += t1;
for (t2=read();t2;t2--) t3 = read(), Add_Edge(i,n+t3,read());
}
for (int i=1;i<=m;i++) Add_Edge(n+i,T,read());
printf("%d\n",vout-Dinic());
return 0;
}
Very soon this web site will be famous amid all
blog users, due to it’s fastidious posts
Aw, this was a very good post. Taking a few minutes and
actual effort to produce a very good article… but what can I say… I hesitate a whole lot and don’t manage to get anything done.
What’s up, I wish for to subscribe for this webpage to obtain most up-to-date updates,
so where can i do it please assist.
I’m really impressed with your writing skills and also with the layout on your blog.
Is this a paid theme or did you customize it
yourself? Anyway keep up the nice quality writing, it’s rare to see
a great blog like this one nowadays.
Great blog! Do you have any suggestions for aspiring writers?
I’m hoping to start my own website soon but I’m a little lost on everything.
Would you recommend starting with a free platform like WordPress
or go for a paid option? There are so many options out there that I’m totally confused ..
Any ideas? Appreciate it!
If you wish for to take a great deal from this piece of writing then you have to apply
such methods to your won website.
Hi, just wanted to mention, I liked this blog post.
It was helpful. Keep on posting!
I got this web page from my pal who informed me about this web site and now this time I am browsing this
web site and reading very informative articles at this place.
Thanks for any other excellent post. Where else may just anybody get
that type of information in such a perfect approach of writing?
I’ve a presentation next week, and I am at the search for
such information.
Thanks for sharing your thoughts about plenty of fish dating site.
Regards
With havin so much content and articles do you ever run into
any issues of plagorism or copyright violation?
My site has a lot of unique content I’ve either authored myself or outsourced but it appears a
lot of it is popping it up all over the internet without my authorization. Do you know any ways to help reduce content from being
stolen? I’d definitely appreciate it.
When I initially left a comment I seem to have clicked on the -Notify
me when new comments are added- checkbox and from now on each time a comment is added I get four emails
with the exact same comment. Perhaps there is an easy method you can remove me from that service?
Thanks!
I’m extremely inspired with your writing abilities and
also with the layout for your weblog. Is this a paid theme or did you
customize it yourself? Either way keep up the nice quality writing, it’s uncommon to
look a nice blog like this one today..
I every time used to study piece of writing in news papers but now as I am a user of web so
from now I am using net for articles or reviews, thanks to web.
Its not my first time to pay a quick visit this
web site, i am visiting this web page dailly and obtain pleasant
data from here daily.
Yesterday, while I was at work, my cousin stole my iphone and tested to
see if it can survive a 30 foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is totally off topic but I had to share it with someone!
I have read so many articles or reviews concerning the blogger lovers
however this piece of writing is actually a
pleasant paragraph, keep it up.
If you are going for best contents like me, simply visit this website every day since it presents quality contents, thanks plenty of fish natalielise
It’s appropriate time to make some plans for the future and it’s time to be happy.
I’ve read this post and if I could I wish to suggest
you some interesting things or tips. Maybe you could write
next articles referring to this article. I want to read even more things about
it!
I’m extremely impressed with your writing skills and also with the layout
on your blog. Is this a paid theme or did you customize it yourself?
Either way keep up the excellent quality writing, it
is rare to see a nice blog like this one
these days.
Wow! This blog looks just like my old one! It’s on a totally different subject but it has pretty
much the same layout and design. Outstanding choice of colors!
natalielise plenty of fish
Hi! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
It’s a shame you don’t have a donate button! I’d most certainly donate to this
superb blog! I suppose for now i’ll settle for bookmarking and
adding your RSS feed to my Google account. I look forward to fresh updates and
will share this site with my Facebook group. Talk soon!
This design is incredible! You definitely know how to keep a reader amused.
Between your wit and your videos, I was almost moved
to start my own blog (well, almost…HaHa!) Great job. I really enjoyed what you had to say,
and more than that, how you presented it. Too cool!
Oh my goodness! Amazing article dude! Thanks,
However I am going through issues with your RSS. I don’t know the reason why
I can’t subscribe to it. Is there anyone else getting the same RSS problems?
Anyone that knows the solution can you kindly respond? Thanks!!
Good day! Do you know if they make any plugins to help with
Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains.
If you know of any please share. Thank you!
I want to to thank you for this great read!! I certainly enjoyed every little bit of it.
I have you book-marked to look at new things you post… pof natalielise
magnificent put up, very informative. I ponder why the opposite experts of this sector do not understand
this. You should proceed your writing. I’m sure,
you have a huge readers’ base already!
It’s really a nice and useful piece of information. I
am happy that you shared this useful information with us.
Please stay us informed like this. Thanks for sharing.
Your means of describing everything in this paragraph is actually pleasant, every
one can without difficulty be aware of it, Thanks a lot.
Pretty! This was a really wonderful article. Thank you
for supplying this info.
Hi there, I enjoy reading all of your article post. I wanted to write a little comment to support you.
If some one wishes to be updated with latest technologies after that
he must be pay a visit this site and be up to date everyday.
Howdy! This is my first visit to your blog! We are a
collection of volunteers and starting a new initiative in a
community in the same niche. Your blog provided us valuable information to work on. You have done
a outstanding job!
What’s Going down i am new to this, I stumbled upon this
I’ve discovered It positively useful and it has helped me out loads.
I hope to contribute & aid different users like its aided me.
Good job.
My family members all the time say that
I am killing my time here at net, however I know I am getting
experience everyday by reading thes good content.
Hey! This is my 1st comment here so I just wanted to
give a quick shout out and say I genuinely enjoy reading through
your blog posts. Can you suggest any other blogs/websites/forums that go
over the same topics? Thanks!
Hey! I just wanted to ask if you ever have any issues with hackers?
My last blog (wordpress) was hacked and I ended up losing several weeks of
hard work due to no back up. Do you have any solutions
to protect against hackers?
Because the admin of this website is working, no question very
quickly it will be famous, due to its quality contents.
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get got an shakiness over that
you wish be delivering the following. unwell unquestionably come
more formerly again since exactly the same nearly very often inside
case you shield this increase.
Hi Dear, are you truly visiting this web page daily,
if so afterward you will definitely get fastidious knowledge.
I’m really impressed with your writing skills and also with the layout on your blog.
Is this a paid theme or did you customize it yourself?
Anyway keep up the excellent quality writing, it’s rare to see a
great blog like this one today.
Howdy! I could have sworn I’ve been to this
site before but after checking through some of the post I realized it’s new to me.
Anyhow, I’m definitely delighted I found it and
I’ll be book-marking and checking back often!
Greetings! Very useful advice in this particular post!
It is the little changes that make the largest changes.
Thanks a lot for sharing!
Wow, fantastic blog layout! How long have you been blogging for?
you made blogging look easy. The overall look of your site is great, as well as the
content!
I get pleasure from, result in I found just what I used to be having
a look for. You’ve ended my 4 day long hunt! God Bless you man. Have a nice
day. Bye
A person essentially assist to make critically articles I’d state.
That is the first time I frequented your website page and up to now?
I amazed with the analysis you made to make this particular put up incredible.
Great process!
certainly like your website however you have to test the spelling on quite a few of your posts.
A number of them are rife with spelling problems and I find it very troublesome to inform the reality nevertheless I will surely come back again.
You made some really good points there. I checked on the net
to learn more about the issue and found most people will go along
with your views on this site.
Hello it’s me, I am also visiting this web site regularly, this web page is really good and
the people are in fact sharing nice thoughts.
Touche. Outstanding arguments. Keep up the great work.
Having read this I believed it was very informative.
I appreciate you spending some time and effort to put this informative article together.
I once again find myself personally spending a
significant amount of time both reading and leaving comments.
But so what, it was still worth it!
Great article, totally what I needed.
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored material stylish.
nonetheless, you command get got an shakiness over that you wish be delivering the following.
unwell unquestionably come more formerly again as exactly the same nearly a
lot often inside case you shield this increase.
I am extremely impressed with your writing skills as well as with the layout
on your blog. Is this a paid theme or did you customize it
yourself? Either way keep up the nice quality writing, it’s rare
to see a great blog like this one these days.
Hi my loved one! I wish to say that this post is awesome, great
written and include approximately all significant infos.
I’d like to peer more posts like this .
Howdy! I could have sworn I’ve been to this web site before but after looking at some of
the posts I realized it’s new to me. Nonetheless, I’m certainly happy I discovered it and I’ll be bookmarking it
and checking back frequently!
It’s very straightforward to find out any topic on web as compared to textbooks,
as I found this piece of writing at this site.
You should take part in a contest for one of the greatest sites
on the net. I am going to highly recommend this website!
Hey there, I think your blog might be having browser compatibility issues.
When I look at your blog site in Chrome, 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, superb
blog!
For latest information you have to pay a quick visit internet and on world-wide-web I found this site as a finest
site for most recent updates.
Awesome things here. I am very happy to look
your article. Thanks so much and I’m having a look forward to contact you.
Will you please drop me a mail?
Hi everyone, it’s my first visit at this web page, and piece of writing is genuinely fruitful in support of me, keep up posting these
articles.
Very nice article, just what I wanted to find.
I couldn’t refrain from commenting. Perfectly written!
Ahaa, its fastidious discussion about this piece of writing at this
place at this website, I have read all that,
so now me also commenting here.
This is a topic that’s close to my heart…
Thank you! Where are your contact details though?
I am really thankful to the owner of this website who has shared this enormous post at here.
What’s up to all, it’s genuinely a nice for me to go
to see this web page, it consists of useful Information.
It’s awesome in favor of me to have a website, which is good in support of
my knowledge. thanks admin
I was very happy to search out this web-site.I needed to thanks in your time for this wonderful learn!! I positively enjoying every little bit of it and I have you bookmarked to take a look at new stuff you blog post.
Hi mates, how is the whole thing, and what you would like to say concerning this paragraph, in my view
its in fact awesome for me.
Wonderful beat ! I would like to apprentice while you amend your web site, how can i subscribe for a blog site?
The account aided me a acceptable deal. I had been a little bit acquainted of
this your broadcast offered bright clear idea
This information is invaluable. When can I find
out more?
No matter if some one searches for his essential thing,
therefore he/she desires to be available that
in detail, thus that thing is maintained
over here.
I every time used to study article in news papers but now as I am a user of net therefore from now I
am using net for posts, thanks to web.
Howdy! This post could not be written any better!
Reading this post reminds me of my previous room mate!
He always kept chatting about this. I will forward this page to him.
Pretty sure he will have a good read. Thank you for sharing!
excellent points altogether, you just gained a new reader.
What may you suggest about your put up that you just made some days in the past?
Any sure?
Way cool! Some extremely valid points! I appreciate
you penning this post and also the rest of the website is very good.
obviously like your web site but you need to check the spelling on quite a few of your
posts. Many of them are rife with spelling issues and I find it
very bothersome to tell the reality then again I will definitely come again again.
I went over this web site and I conceive you have a lot of fantastic information, saved to bookmarks (:.