Poj 2516 Minimum Cost (最小花费最大流)

时间：2022-07-26 05:32:54

题目链接：

　　Poj  2516  Minimum Cost

题目描述：

　　有n个商店，m个仓储，每个商店和仓库都有k种货物。嘛！现在n个商店要开始向m个仓库发出订单了，订单信息为当前商店对每种货物的需求量。不同的商店从不同的仓库购买不同货物花费不同，问是不是能满足所有商店的要求，如果能商店花费总和最小为多少？

解题思路：

　　简单的费用流，要跑K次最小花费最大流，每次只对一种货物建图跑费用流。每次建图以0为源点, [1,m]为仓库, [m+1, n+m]为商店, n+m+1为汇点。0与[1,m]连边，边容量为仓库存货，边单位流量的花费为0。

[1,m]与[m+1,n+m]连边，边容量为INF，边单位流量的花费为对应仓库供应i货物给对应商店的单位花费。[m+1,n+m]与汇点连边，边容量为商店需求，边单位流量的花费为0。这个题目建图时候的初始化一定要搞好，不然很容易TLE。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 int flow[maxn][maxn], cap[maxn][maxn];

 int shop[maxn][maxn], supply[maxn][maxn];

 int vis[maxn], pre[maxn], dis[maxn], cost[maxn][maxn];

 int c, Flow, s, e;

 bool spfa ()

 {

     queue <int> Q;

     for (int i=s; i<=e; i++)

     {

         dis[i] = INF;

         vis[i] = ;

     }

     dis[] = ;

     vis[] = ;

     Q.push (s);

     while (!Q.empty())

     {

         int u = Q.front();

         Q.pop();

         vis[u] = ;

         for (int v=s; v<=e; v++)

         {

             if (cap[u][v]>flow[u][v] && dis[v]>dis[u]+cost[u][v])

             {

                 dis[v] = dis[u] + cost[u][v];

                 pre[v] = u;

                 if (!vis[v])

                 {

                     vis[v] = ;

                     Q.push(v);

                 }

             }

         }

     }

     if (dis[e] == INF)

         return false;

     return true;

 }

 void MincostMaxflow ()

 {

     memset (flow, , sizeof(flow));

     c = Flow = ;

     while (spfa())

     {

         int Min = INF;

         for (int i=e; i!=s; i=pre[i])

             Min = min (Min, cap[pre[i]][i]-flow[pre[i]][i]);

         for (int i=e; i!=s; i=pre[i])

         {

             flow[pre[i]][i] += Min;

             flow[i][pre[i]] -= Min;

         }

         Flow += Min;

         c += Min * dis[e];

     }

 }

 int main ()

 {

     int n, m, k;

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

     {

         int flag, Cost;

         flag = Cost = s = , e = n + m + ;

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

             for (int j=; j<=k; j++)

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

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

             for (int j=; j<=k; j++)

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

         memset (cap, , sizeof(cap));

         memset (cost, , sizeof(cost));

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

             for (int j=m+; j<=n+m; j++)

                 cap[i][j] = INF;

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

         {

             int total = ;

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

                 for (int l=; l<=m; l++)

                 {

                     scanf ("%d", &cost[l][j+m]);

                     cost[j+m][l] = -cost[l][j+m];

                 }

             if (flag)

                 continue;

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

                 {

                     cap[j+m][e] = shop[j][i];

                     total += shop[j][i];

                 }

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

                 cap[s][j] = supply[j][i];

             MincostMaxflow();

             if (Flow < total)

                 flag = ;

             Cost += c;

         }

         printf ("%d\n", flag?-:Cost);

     }

     return ;

 }

相关文章