纠结了很久的一道题目，从拿到题目开始就没有想法， 再到看了几天才看懂了怎么做。 为了看懂题解我还特意去看了看线性规划，这题确实不简单。这建图的思路很值得学习!

关于题解， 网上有大神的详细解题报告，如果想彻底的搞懂建议去看点线性规划基础的东西，不然会对其中的松弛操作，还有不等式的建立搞不清楚。

我的理解，首先看到题目就可以知道这个必定和线性规划有关， 整个就一个线性规划的模型， 然后自然的就会列出不等式，进行松弛操作。  在得到一组等式后， 又可以想到的是， 那种用网络流求解不等式的方法， 当时要满足其中的变量要正负都出现一次， 然后等式两两相减，最后就是建图， 用最小费用流求解了。 

 

1061: [Noi2008]志愿者招募

Time Limit: 20 Sec  

Memory Limit: 162 MB

Submit: 892  

Solved: 561

[ ][ ][ ]

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

14

HINT

招募第一类志愿者3名，第三类志愿者4名 

30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 

100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 

不超过2^31-1。

Source

 

[ ][ ][ ]

 

---

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 1100#define M 1000010#define INF 0x3fffffffstruct node{    int to,next,w,c;}edge[M];int n,m;int save[N];int cnt,pre[N];int s,t;int point[N],pedge[N];int que[2*M];void add_edge(int u,int v,int w,int c){    edge[cnt].to=v;    edge[cnt].w=w;    edge[cnt].c=c;    edge[cnt].next=pre[u];    pre[u]=cnt++;}void init(){    cnt=0;    memset(pre,-1,sizeof(pre));    memset(save,0,sizeof(save));    for(int i=1;i<=n;i++)        scanf("%d",&save[i]);    for(int i=0;i
        
         0)          {            add_edge(s,i,tmp,0);            add_edge(i,s,0,0);        }        else        {            add_edge(i,t,-tmp,0);            add_edge(t,i,0,0);        }        if(i!=1)        {            add_edge(i,i-1,INF,0);            add_edge(i-1,i,0,0);        }    }}// 建好了图，然后就是最小费用最大流了...int SPFA(){    int dis[N],mark[N],cnt[N];    int qf=1,qd=0,flag=0;    memset(cnt,0,sizeof(cnt));    memset(point,-1,sizeof(point));    memset(pedge,-1,sizeof(pedge)); // 这里因为边没有记录上一个边所以要记录点和边        for(int i=0;i
         
          qd)    {        int cur=que[qd++];        mark[cur]=0;        cnt[cur]++;        if(cnt[cur] > n+2)        {            flag=1;            break;        }        for(int p=pre[cur];p!=-1;p=edge[p].next)        {            if(edge[p].w==0) continue;            int v=edge[p].to,w=edge[p].c;            if( dis[v] > dis[cur]+w )            {                point[v]=cur;                pedge[v]=p;                dis[v]=dis[cur]+w;                if( mark[v]==0 )                {                    mark[v]=1;                    que[qf++]=v;                }            }        }    }    if(dis[t]==INF||flag==1) return 0;    else return 1;}int cal(){    int mi=INF;    int tmp=t;    while(tmp!=s)    {        if(edge[pedge[tmp]].w