设为首页 加入收藏

TOP

POJ 2516 Minimum Cost 费用流(二)
2012-11-03 14:39:57 来源: 作者: 【 】 浏览:750
Tags:POJ  2516  Minimum  Cost  费用

    while(path[pre]!=-1)//调整流量

    {

    f[path[pre]][pre]+=maxFlow;

    f[pre][path[pre]]=-f[path[pre]][pre];

    pre=path[pre];

    }

    }

    }

    int need[Max][Max],have[Max][Max];

    int cost[Max][Max][Max];

    int main()

    {

    int i,j,k,l,n,m,d;

    while(scanf("%d%d%d",&n,&m,&k),(n+m+k))

    {

    for(i=1; i<=n; i++) //客人i

    for(j=1; j<=k; j++) //需要货物j的数量

    scanf("%d",&need[i][j]);

    for(i=1; i<=m; i++) //仓库i

    for(j=1; j<=k; j++) //有货物j的数量

    scanf("%d",&have[i][j]);

    for(i=1; i<=k; i++) //第i个商品

    for(j=1; j<=n; j++) //送到j地点

    for(d=1; d<=m; d++) //从d地点的

    scanf("%d",&cost[i][d][j]);//的费用

    S=0,T=n+m+1;//超级源点0,超级汇点n+m+1;

    //cout《1《endl;

    bool flag=0;

    int ans=0;

    for(i=1; i<=k; i++)

    {

    memset(c,0,sizeof(c));

    memset(f,0,sizeof(f));

    memset(w,0,sizeof(w));

    for(j=1; j<=m; j++)//源点到每个仓库的容量为该仓库这种物品的存量

    c[0][j]=have[j][i];

    for(j=1; j<=n; j++)//每个客人到汇点的容量为该客人对物品的需求量

    c[m+j][T]=need[j][i];

    for(j=1; j<=m; j++)

    for(d=1; d<=n; d++)

    c[j][d+m]=have[j][i];//每个仓库到每个客人之间的容量为该仓库这种物品的存量

    for(j=1; j<=m; j++)

    for(d=1; d<=n; d++)

    w[j][d+m]=cost[i][j][d],w[d+m][j]=-w[j][d+m];//花费,负花费用于回流

    getMaxflow();

    //cout《1《endl;

    for(j=1; j<=n; j++)

    if(c[j+m][T]!=f[j+m][T])//如果不能供货,则输出-1

    {

    flag=1;

    break;

    }

    if(flag)

    break;

    for(j=1; j<=m; j++)

    for(d=1; d<=n; d++)

    ans+=f[j][d+m]*w[j][d+m];//总费用

    // cout《1《endl;

    }

    if(flag)

    cout《"-1"《endl;

    else

    cout《ans《endl;

    }

    return 0;

    }

      

首页 上一页 1 2 3 下一页 尾页 2/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇字符串字典顺序比较 下一篇CBuilder高手进阶(一)编写弹出..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: