min_cost_max_flow.cpp

这是关于图论算法里面的一些代码,图论基本的思想代码的实现

////////////////////////////////begin////////////////////////////////////////////////////////
int mincostmaxflow()
{
    int now,kk;
    int max =0,tmp;
    while(1)
    {
        i = 0,j=0;
        que[0]=0;
        for(now=0;now<=total;now++)
         pre[now]=-1,min[now]=0;
        path[0]=INF;
        while(i<=j)
        {
            now = que[i++];
            for(kk=0;kk<=total;kk++)
             if(use[now][kk] > value[now][kk] && (pre[kk]<0||min[kk] > price[now][kk]+ min[now]))
             {
                 min[kk] = price[now][kk]+ min[now];
                 pre[kk]=now;
                 que[++j]=kk;
                 path[kk] = path[now]>(tmp=use[now][kk] - value[now][kk])?tmp:path[now];                 
             }else if(value[kk][now] > 0 && (pre[kk]<0||min[kk] > min[now]-price[kk][now]))
             {
                 min[kk] = min[now]-price[kk][now];
                 que[++j]=kk;
                 pre[kk]=now+total;
                 path[kk] = path[now]>(tmp=value[kk][now])?tmp:path[now];
             }
        }
        if(pre[total]==-1)
          break;
        i = total;
        while(i!=0)
        {
            j = pre[i];
            if(j>total){
             j-=total;value[i][j]-=path[total];
            }     
            else
             value[j][i]+=path[total];
            i = j;
        }
        max += path[total]*min[total];
    }
    for(i=1;i<=n;i++)
     if(value[i+m][total]!=use[i+m][total])
       return find =false;
    return max;
}
//////////////////////////////////end//////////////////////////////////////////////////////////////



//-----------------------------------------begin--------------------------------------------------
int min_cost_max_flow(int n,int mat[][MAXN],int cost[][MAXN],
                      int source,int sink,int flow[][MAXN],int& netcost){
    int pre[MAXN],min[MAXN],d[MAXN],i,j,t,tag;
    if (source==sink) return inf;
    for (i=0;i<n;i++)
        for (j=0;j<n;flow[i][j++]=0);
    for (netcost=0;;){
        for (i=0;i<n;i++)
            pre[i]=0,min[i]=inf;
        for (pre[source]=source+1,min[source]=0,d[source]=inf,tag=1;tag;)
            for (tag=t=0;t<n;t++)
                if (d[t]) for (i=0;i<n;i++)
                     if (j=mat[t][i]-flow[t][i]&&min[t]+cost[t][i]<min[i])
                tag=1,min[i]=min[t]+cost[t][i],pre[i]=t+1,d[i]=d[t]<j?d[t]:j;
                     else if (j=flow[i][t]&&min[t]-cost[i][t]<min[i])
                tag=1,min[i]=min[t]-cost[i][t],pre[i]=-t-1,d[i]=d[t]<j?d[t]:j;
        if (!pre[sink]) break;
        for (netcost+=min[sink]*d[i=sink];i!=source;)
            if (pre[i]>0)
                flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
            else
                flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
    }
    for (j=i=0;i<n;j+=flow[source][i++]);
    return j;
}

//-----------------------------------------end----------------------------------------------------