[NOI 2008 day1 志愿者招募]最小费用最大流、利用不等式构造等式、利用流量守恒保证可行解**

【题目】

【算法分析】

详细的看这里吧：http://www.byvoid.com/blog/noi-2008-employee/

【其它】最后一个点在我机器上TLE。。。BYV大牛的程序也是。。。算了，都差不了多少秒。

【CODE】

#include #include const int N=1111;
const int M=11111;
const int E=100000;
const int inf=0x7FFFFFFF;
struct gtp{int x,y,next,op,c,w;}g[E];
int n,m,S,T,e,cost,flow,tot;
int need[N],st[M],ed[M],cc[M];
int ls[N],d[N],fa[N],list[N],v[N],zz[N];

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&need[i]);
    for (int i=1;i<=m;i++)
      scanf("%d%d%d",&st[i],&ed[i],&cc[i]);
}  

void add(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].op=e+1;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].op=e-1;
    g[e].next=ls[y]; ls[y]=e;
}   

void build(){
    S=n+2; T=n+3;
    for (int i=0;i<=n;i++)
      if (need[i]-need[i+1]>0) add(S,i+1,need[i]-need[i+1],0);
                          else add(i+1,T,need[i+1]-need[i],0);
    for (int i=2;i<=n+1;i++) add(i-1,i,inf,0);
    for (int i=1;i<=m;i++)
      add(ed[i]+1,st[i],inf,cc[i]);
}   

bool spfa(){
    memset(d,50,sizeof(int)*(T+1));
    tot=0;
    d[S]=0;
    int head=0,tail=1; list[1]=S;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }   
          }   
        v[list[head]]=0;
    }   
    if (d[T]!=d[0]) return true;
    return false;
}   

void change(){
    int nf=inf;
    for (int i=T;i!=S;i=g[fa[i]].x)
      if (g[fa[i]].c    cost+=nf*d[T];
    flow+=nf;
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }   
}   

void maxflow_mincost(){
    flow=0; cost=0;
    while (spfa())
      change();
    printf("%dn",cost);
}   

int main(){
    init();
    build();
    maxflow_mincost();
    return 0;
}