【费用流】BZOJ1061[NOI2008]-志愿者招募

【题目大意】

一个项目需要n天完成，其中第i天至少需要Ai个人。共有m类人可以招募，其中第i类可以从第Si天做到第Ti天，每人的招募费用为Ci元。求最小招募费用。

【思路】

byvoid神犇的建图详解，对理解网络流有很好的帮助，下面再引用一下，原po请戳：★

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define S 0

 #define T n+2

 using namespace std;

 struct node

 {

     int to,pos,cap,val;

 };

 const int MAXM=+;

 const int MAXN=+;

 const int INF=0x7fffffff;

 int n,m,a[MAXN],s[MAXM],t[MAXM],c[MAXM];

 int pre[MAXN],preedge[MAXN];

 vector<node> E[MAXN];

 void addedge(int u,int v,int ca,int va)

 {

     E[u].push_back((node){v,E[v].size(),ca,va});

     E[v].push_back((node){u,E[u].size()-,,-va});

 }

 int SPFA()

 {

     queue<int> que;

     int vis[MAXN],dis[MAXN];

     memset(vis,,sizeof(vis));

     memset(pre,-,sizeof(pre));

     for (int i=S;i<=T;i++) dis[i]=INF;

     que.push();

     vis[]=;

     dis[]=;

     while (!que.empty())

     {

         int head=que.front();que.pop();

         vis[head]=;

         for (int i=;i<E[head].size();i++)

         {

             node &tmp=E[head][i];

             if (tmp.cap> && dis[tmp.to]>dis[head]+tmp.val)

             {

                 dis[tmp.to]=dis[head]+tmp.val;

                 pre[tmp.to]=head;

                 preedge[tmp.to]=i;

                 if (!vis[tmp.to])

                 {

                     que.push(tmp.to);

                     vis[tmp.to]=;

                 }

             }

         }

     }

     if (dis[T]==INF) return ;else return ;

 }

 int mcf()

 {

     int flow=;

     int ans=;

     while (SPFA())

     {

         int f=INF;

         for (int i=T;pre[i]!=-;i=pre[i])

         {

             node &tmp=E[pre[i]][preedge[i]];

             f=min(f,tmp.cap);

         }

         for (int i=T;pre[i]!=-;i=pre[i])

         {

             node &tmp=E[pre[i]][preedge[i]];

             tmp.cap-=f;

             E[tmp.to][tmp.pos].cap+=f;

             ans+=f*tmp.val;

         }

     }

     return ans;

 }

 void init()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     for (int i=;i<=m;i++) scanf("%d%d%d",&s[i],&t[i],&c[i]);

 }

 void build()

 {

     a[]=a[n+]=;

     for (int i=;i<=n+;i++)

     {

         int c=a[i]-a[i-];

         if (c>) addedge(S,i,c,);

         if (c<) addedge(i,T,-c,);

     }

     for (int i=;i<=m;i++)

         addedge(s[i],t[i]+,INF,c[i]);

     for (int i=;i<=n;i++) addedge(i+,i,INF,);

 }

 int main()

 {

     init();

     build();

     cout<<mcf()<<endl;

     return ;

 }