【BZOJ 1061】 1061: [Noi2008]志愿者招募 （线性规划与网络流）**

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 1010
  9 #define Maxm 10010
 10 #define INF 0xfffffff
 11 
 12 int mymin(int x,int y) {return x<y?x:y;}
 13 
 14 int n,m;
 15 
 16 struct node
 17 {
 18     int x,y,f,c,o,next;
 19 }t[4*Maxm];
 20 int first[Maxn],len;
 21 
 22 void ins(int x,int y,int f,int c)
 23 {
 24     t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;t[len].o=len+1;
 25     t[len].next=first[x];first[x]=len;
 26     t[++len].x=y;t[len].y=x;t[len].f=0;t[len].c=-c;t[len].o=len-1;
 27     t[len].next=first[y];first[y]=len;
 28 }
 29 
 30 int nd[Maxn];
 31 int dis[Maxn],flow[Maxn],pre[Maxn],st,ed;
 32 bool inq[Maxn];
 33 queue<int > q;
 34 
 35 void bfs()
 36 {
 37     while(!q.empty()) q.pop();
 38     // memset(dis,-1,sizeof(dis));
 39     for(int i=1;i<=ed;i++) dis[i]=INF;
 40     memset(inq,0,sizeof(inq));
 41     dis[st]=0;inq[st]=1;q.push(st);
 42     flow[st]=INF;
 43     while(!q.empty())
 44     {
 45         int x=q.front();
 46         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 47         {
 48             int y=t[i].y;
 49             if(dis[y]>dis[x]+t[i].c)
 50             {
 51                 dis[y]=dis[x]+t[i].c;
 52                 pre[y]=i;
 53                 flow[y]=mymin(flow[x],t[i].f);
 54                 if(!inq[y])
 55                 {
 56                     q.push(y);
 57                     inq[y]=1;
 58                 }
 59             }
 60         }
 61         q.pop();inq[x]=0;
 62     }
 63 }
 64 
 65 void max_flow()
 66 {
 67     int sum=0;
 68     while(1)
 69     {
 70         bfs();
 71         if(dis[ed]==INF) break;
 72         sum+=dis[ed]*flow[ed];
 73         int x=ed;
 74         while(x!=st)
 75         {
 76             t[pre[x]].f-=flow[ed];
 77             t[t[pre[x]].o].f+=flow[ed];
 78             x=t[pre[x]].x;
 79         }
 80     }
 81     printf("%d\n",sum);
 82 }
 83 
 84 void output()
 85 {
 86     for(int i=1;i<=len;i+=2)
 87     {
 88         printf("%d -> %d = %d , %d \n",t[i].x,t[i].y,t[i].f,t[i].c);
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     scanf("%d%d",&n,&m);
 95     len=0;
 96     for(int i=1;i<=n;i++) scanf("%d",&nd[i]);
 97     memset(first,0,sizeof(first));
 98     for(int i=1;i<=m;i++)
 99     {
100         int l,r,c;
101         scanf("%d%d%d",&l,&r,&c);
102         ins(l,r+1,INF,c);
103     }
104     for(int i=1;i<=n;i++) ins(i+1,i,INF,0);
105     nd[0]=0;
106     st=n+2;ed=st+1;
107     for(int i=1;i<=n;i++) if(nd[i]-nd[i-1]>0) ins(st,i,nd[i]-nd[i-1],0);
108     else if(nd[i]-nd[i-1]<0) ins(i,ed,nd[i-1]-nd[i],0);
109     ins(n+1,ed,nd[n],0);
110     // output();
111     max_flow();
112     return 0;
113 }