时间戳

首页 > 技术文章 > E - Minimum Cost - POJ 2516（最小费）

E - Minimum Cost - POJ 2516（最小费）

liuxin13 2015-08-09 18:41 原文

题目大意：N个客户，M个供货商，K种商品，现在知道每个客户对每种商品的需求量，也知道每个供货商每种商品的持有量，和供货商把一种商品运送到每个客户的单位花费。现在想知道如果能满足所有客户的最小花费是多少，如果不能满足输出 -1
输入详解：（图片引用源自http://blog.csdn.net/lyy289065406/article/details/6742534）。

分析：第一次做的时候想到把供应商的每种商品和客户的需求的每种商品直接连接然后求最大流，不过CE了，想着数据都是50也不大，不过仔细一想 50*50*50那就很大了，我的数组只开了500....然后想了一下觉得边是非常少的于是换成了邻接矩阵储存，然后果断给了一个TLE，下面是超时代码

#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

const int MAXN = 120007;
const int oo = 1e9+7;

struct Edge{int u, v, flow, cost, next;}edge[MAXN*10];
int Head[MAXN], cnt, pre[MAXN], dist[MAXN];
bool inqueue[MAXN];
void AddEdge(int u, int v, int flow, int cost)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].flow = flow;
    edge[cnt].cost = cost;
    edge[cnt].next = Head[u];
    Head[u] = cnt++;
}

bool spfa(int start, int End)
{
    queue<int> Q;Q.push(start);

    for(int i=1; i<=End; i++)
        dist[i] = oo, pre[i]=-1;
    dist[start] = 0;

    while(Q.size())
    {
        int u = Q.front();Q.pop();
        inqueue[u] = false;

        for(int i=Head[u]; i != -1; i=edge[i].next)
        {
            int v = edge[i].v;

            if(edge[i].flow && dist[v] > dist[u]+edge[i].cost)
            {
                dist[v] = dist[u] + edge[i].cost;
                pre[v] = i;

                if(!inqueue[v])
                {
                    inqueue[v] = true;
                    Q.push(v);
                }
            }
        }
    }

    return dist[End] != oo;
}
void MinCost(int start, int End, int needFlow)
{
    int i, MaxFlow = 0, cost=0;

    while(spfa(start, End) == true)
    {
        int MinFlow = oo;

        for(i=pre[End]; i != -1; i=pre[edge[i].u])
            MinFlow = min(MinFlow, edge[i].flow);
        for(i=pre[End]; i != -1; i=pre[edge[i].u])
        {
            edge[i].flow -= MinFlow;
            edge[i^1].flow += MinFlow;
            cost += edge[i].cost;
        }

        MaxFlow += MinFlow;
    }

    if(MaxFlow != needFlow)
        printf("-1\n");
    else
        printf("%d\n", cost);
}

int main()
{
    int N, M, K;

    while(scanf("%d%d%d", &N, &M, &K), N+M+K)
    {
        int i, j, k, x, needFlow=0;
        int start = (N+M)*K+1, End = start+1;

        for(i=1; i<=End; i++)
            Head[i] = -1;
        cnt = 0;

        for(i=0; i<N; i++)
        for(j=1; j<=K; j++)
        {///每个客户i需要的商品j的数量,建立汇点和需求量的关系
            scanf("%d", &x);

            int nk = i*K+j;///这个客户需求的商品的编号

            AddEdge(nk, End, x, 0);
            AddEdge(End, nk, 0, 0);
            needFlow += x;
        }

        for(i=0; i<M; i++)
        for(j=1; j<=K; j++)
        {///每个供货商i所有的商品j的数量，建立源点与供货商的关系
            scanf("%d", &x);

            int mk = (N+i)*K + j;///供货商i的商品j的编号

            AddEdge(start, mk, x, 0);
            AddEdge(mk, start, 0, 0);
        }

        for(k=1; k<=K; k++)
        for(i=0; i<N; i++)
        for(j=0; j<M; j++)
        {///供货商j把货物k送到客户i需要的花费
            scanf("%d", &x);

            int nk = i*K+k;///客户i需要的k编号
            int mk = (N+j)*K+k;///供货商j的货物k的编号

            AddEdge(mk, nk, oo, x);
            AddEdge(nk, mk, 0, -x);
        }

        MinCost(start, End, needFlow);
    }

    return 0;
}
View Code

然后就有些不知该怎么搞，只能向大神求助，看了别人的思路，原来这是多源多汇的费用流问题，看到这里也就明白了怎么做把K种商品拆开，对每一种商品进行最小费处理，这样图只有100*100,然后最多操作50次，很容易就求出来了结果。下面是AC代码。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

const int MAXN = 105;
const int oo = 1e9+7;

struct Graph{int cost, flow;}G[MAXN][MAXN];
int need[MAXN][MAXN];///客户对每种商品的需求量
int have[MAXN][MAXN];///供货商对每种商品的持有量

bool spfa(int pre[], int start, int End)
{
    stack<int> sta; sta.push(start);
    int i, u, dist[MAXN], instack[MAXN]={0};

    for(i=1; i<=End; i++)
        dist[i] = oo;
    dist[start] = 0;

    while(sta.size())
    {
        u = sta.top();sta.pop();
        instack[u] = false;

        for(i=1; i<=End; i++)
        {
            if(G[u][i].flow && dist[i] > dist[u]+G[u][i].cost)
            {
                dist[i] = dist[u] + G[u][i].cost;
                pre[i] = u;

                if(instack[i] == false)
                {
                    instack[i] = true;
                    sta.push(i);
                }
            }
        }
    }

    return dist[End] == oo ? false : true;
}
int MinCost(int start, int End, int needFlow)
{
    int i, MaxFlow=0, cost=0, pre[MAXN]={0};

    while(spfa(pre, start, End) == true)
    {
        int MinFlow = oo;

        for(i=End; i!=start; i=pre[i])
            MinFlow = min(MinFlow, G[pre[i]][i].flow);
        for(i=End; i!=start; i=pre[i])
        {
            int k = pre[i];
            G[k][i].flow -= MinFlow;
            G[i][k].flow += MinFlow;
            cost += MinFlow * G[k][i].cost;
        }

        MaxFlow += MinFlow;
    }

    if(MaxFlow != needFlow)
        cost = -1;

    return cost;
}

int main()
{
    int N, M, K;

    while(scanf("%d%d%d", &N, &M, &K), N+M+K)
    {
        int i, j, k, x, needCost=0;

        for(i=1; i<=N; i++)
        for(j=1; j<=K; j++)
        {///输入客户i对第j种商品的需求量
            scanf("%d", &need[i][j]);
        }

        for(i=1; i<=M; i++)
        for(j=1; j<=K; j++)
        {///供货商i对第j种商品的持有量
            scanf("%d", &have[i][j]);
        }

        bool ok = true;

        for(k=1; k<=K; k++)
        {///第k种商品

            memset(G, 0, sizeof(G));

            for(i=1; i<=N; i++)
            for(j=1; j<=M; j++)
            {///客户所在的区间为 M~N+M
                scanf("%d", &x);
                G[j][M+i].cost = x;
                G[M+i][j].cost = -x;
                G[j][M+i].flow = oo;
            }

            if(ok == true)
            {
                int start = M+N+1, End = start+1;
                int needFlow = 0;///需要第k种商品的量

                for(i=1; i<=M; i++)
                {///建立源点与供货商间的关系
                    G[start][i].flow = have[i][k];
                }
                for(i=1; i<=N; i++)
                {///建立客户与汇点之间的关系
                    G[M+i][End].flow = need[i][k];
                    needFlow += need[i][k];
                }

                int cost = MinCost(start, End, needFlow);

                if(cost == -1)
                    ok = false;
                else
                    needCost += cost;
            }
        }

        if(ok == false)
            needCost = -1;
        printf("%d\n", needCost);
    }

    return 0;
}
View Code

推荐阅读