【BZOJ 1061】[Noi2008] 志愿者招募

题目传送门: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;
}

22 thoughts to “【BZOJ 1061】[Noi2008] 志愿者招募”

  1. 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.

  2. 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!

  3. 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.

  4. 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!

  5. 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!

  6. 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.

  7. 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!

  8. 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!

  9. 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.

  10. 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!

  11. 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.

Leave a Reply to sling tv Cancel reply

Your email address will not be published. Required fields are marked *