题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1061
这题好神……
作为单纯形的例题,用费用流给艹过去……
题解的话,我已经膜拜得五体投地了,让我们召唤BYvoid:https://www.byvoid.com/blog/noi-2008-employee/
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000+9; const int M = 100000; const int INF = 1e9; int head[N],nxt[M],to[M],flow[M],cost[M],dis[N]; int n,m,S,T,ned[N],inq[N],sur[N],FLOW[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 int SPFA() { memset(dis,127,sizeof(dis)); memset(FLOW,0,sizeof(FLOW)); que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF; 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[w] + cost[i] < dis[to[i]]) { dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i; FLOW[to[i]] = min(FLOW[w], flow[i]); if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1; } } return FLOW[T]; } inline int MCMF() { int ret = 0; for (int w=T,f;f=SPFA();w=T) for (int t=sur[w];w!=S;t=sur[w]) flow[t] -= f, flow[t^1] += f, ret += cost[t]*f, w = to[t^1]; return ret; } int main(){ n = read(); m = read(); S = 0; T = N-1; for (int i=1;i<=n;i++) ned[i] = read(); for (int i=n+1;i;i--) ned[i] = ned[i-1] - ned[i]; for (int i=1;i<=n+1;i++) if (ned[i] > 0) Add_Edge(S,i,ned[i],0); else Add_Edge(i,T,-ned[i],0); for (int i=1;i<=n;i++) Add_Edge(i,i+1,INF,0); for (int i=1,s,t,c;i<=m;i++) s = read(), t = read(), c = read(), Add_Edge(t+1,s,INF,c); printf("%d\n",MCMF()); return 0; }
This is one awesome blog.Thanks Again. Awesome.
Wonderful site. Plenty of useful info here. I am sending it to several friends ans also sharing in delicious.
And certainly, thank you in your effort!
Hi there! Someone in my Facebook group shared this
site with us so I came to give it a look. I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to my followers!
Excellent blog and outstanding design.
Quality articles is the crucial to be a focus for the visitors to
pay a visit the web page, that’s what this website is providing.
I visited several websites except the audio feature
for audio songs current at this web site is genuinely fabulous.
Quality articles is the crucial to attract the visitors to pay
a quick visit the website, that’s what this site is providing.
Wow! This blog looks just like my old one! It’s on a entirely different subject but it
has pretty much the same layout and design. Excellent choice of colors!
you’re actually a good webmaster. The site loading
velocity is amazing. It sort of feels that you’re doing
any distinctive trick. Also, The contents are
masterwork. you have done a fantastic job
in this subject!
Hello, i read your blog occasionally and i own a
similar one and i was just curious if you get a lot of
spam responses? If so how do you protect against it, any plugin or anything you can advise?
I get so much lately it’s driving me mad so any assistance is very much
appreciated.
Hi! This post could not be written any better!
Reading through this post reminds me of my previous
room mate! He always kept chatting about this. I will forward this article to him.
Fairly certain he will have a good read. Thank you
for sharing!
It’s remarkable to pay a quick visit this web site and reading the views of all colleagues about this article, while I am also
eager of getting know-how.
My brother recommended I might like this web site.
He was entirely right. This post actually made
my day. You cann’t believe simply how much time I had spent for this information! Thanks!
Hello there, I found your web site by means of Google whilst searching for a comparable subject, your site came up, it looks good. I have bookmarked it in my google bookmarks.
Hi there mates, its enormous post regarding tutoringand fully defined, keep it up all the time.
Wow, this piece of writing is nice, my younger sister is analyzing these kinds of things, therefore I am going
to convey her.
I was recommended this web site by my cousin. I’m not sure whether this post is
written by him as no one else know such detailed about my trouble.
You are incredible! Thanks!
Excellent blog you have here but I was wanting
to know if you knew of any forums that cover the same topics talked about in this article?
I’d really love to be a part of online community where I can get suggestions from other experienced
individuals that share the same interest. If you have any suggestions, please let me know.
Thanks a lot!
Wow, fantastic blog layout! How long have you been blogging for?
you made blogging look easy. The overall look of your website is fantastic, let alone the content!
Link exchange is nothing else but it is simply placing the other person’s blog link on your page at appropriate place and other person will also do same for you.
Hi there are using WordPress for your blog platform? I’m new to the
blog world but I’m trying to get started and create my own. Do you need any coding knowledge to make your own blog?
Any help would be greatly appreciated!
It’s hard to come by experienced people in this particular topic, but you sound like
you know what you’re talking about! Thanks
Thank you for sharing excellent informations. Your web-site is very cool. I’m impressed by the details that you have on this site. It reveals how nicely you perceive this subject. Bookmarked this web page, will come back for more articles. You, my pal, ROCK! I found simply the info I already searched everywhere and simply could not come across. What an ideal website.