bzoj2879(动态加边费用流)

参考题解：http://blog.csdn.net/yxuanwkeith/article/details/52254602

//开始跑费用流用的dijkstra,一直错,后来发现动态加边后我不会处理势函数；

//因为加进一些边后1号点到某个点的最短路不好更新，有些点是有势函数的,有些没有,图不平衡了;

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=;

int head,tail,q[maxn],H[maxn],last[maxn],inf,All,S,T,n,m,Min,t[][],vis[maxn],dis[maxn],in[maxn],p[],cnt;

struct edg{

    int nxt,to,f,c;

}e[maxn*];

void insert(int x,int y,int z,int zz){

    ++cnt;e[cnt].nxt=last[x];last[x]=cnt;e[cnt].to=y;e[cnt].f=z;e[cnt].c=zz;

}

void add(int x,int k){

    //加第x个厨师的第k组边

    int u=(x-)*All+k;

    if(k>All||vis[u])return;

    vis[u]=;

    insert(S,u,,);insert(u,S,,);

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

    {insert(u,All*m+i,,t[i][x]*k);insert(All*m+i,u,,-t[i][x]*k);}

}

int dfs(int x,int h){

    if(x==T){Min+=dis[T]*h;return h;}

    int tmp=,cp;in[x]=;

    for(int i=last[x];i;i=e[i].nxt){

        int v=e[i].to;

        if(dis[v]==dis[x]+e[i].c&&e[i].f&&!in[v]){

            cp=dfs(v,min(h-tmp,e[i].f));

            e[i].f-=cp;e[i^].f+=cp;tmp+=cp;

            if(tmp==h){//动态加边：当前点跑满流了就新加边；

                //注意加边的顺序，先加费用小的；

                if(x<=All*m&&x!=S)add((x-)/All+,(x-)%All+);

                return tmp;

            }

        }

    }

    return tmp;

}

void solve(){

    while(){

        memset(in,,sizeof(in));memset(dis,,sizeof(dis));

        inf=dis[];dis[S]=;head=tail=;

        q[++tail]=S;

        while(head!=tail){

            head=(head+)%maxn;

            int u=q[head];

            for(int i=last[u];i;i=e[i].nxt){

                int v=e[i].to;

                if(e[i].f&&dis[v]>dis[u]+e[i].c){

                    dis[v]=dis[u]+e[i].c;

                    if(!in[v]){

                        in[v]=;tail=(tail+)%maxn;

                        q[tail]=v;

                    }

                }

            }

            in[u]=;

        }

        if(dis[T]==inf)return;

        dfs(S,inf);

    }

}

int main(){

    cin>>n>>m;

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

        scanf("%d",&p[i]);All+=p[i];

    }

    S=,T=m*All+n+;

    cnt=;

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

        insert(All*m+i,T,p[i],);

        insert(T,All*m+i,,);

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

    }

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

    solve();

    cout<<Min;

    system("pause");

    return ;

}