poj 2516 Minimum Cost 【最小费用最大流】

雨点打透心脏的1/2处 2022-08-13 05:29 205阅读 0赞

题目：[poj 2516 Minimum Cost][]

题意：有 n 个商店，k种物品和 m 个供货商，让你求进满足商店需求的货物的最小花费？

有必要说一下输入数据。

首先n ，k ，m

然后是一个n\*m的矩阵，n个商店对每种货物的需求，表示第 i 个商店需要第 j 种货物 x个

然后是m \* k 的矩阵，m个供货商可以供k种货物的数量，表示第 i 个供货商 提供第 j 中货物 x 个

接下来是 k 个 n \* m 的矩阵，表示第 i 个货物，由 k 供应商发货给 j 商店的价格x

（注意如果供不应求的或输出-1）

分析：很明显能看出来是最小费用最大流，但是如果直接建图的话需要拆点，把每个物品拆成 n 个，分别表示给那个商店，据说会超时，没有试。

从给出的 k 个矩阵，可以看出来可以分开来求，每一个物品来求，然后求和

那么对于第 k 个物品

我们首先

s连接每个商店 ，容量为商店需求，费用0

然后商店到供货商，容量inf ，费用为进价x

然后供货商到 t ，容量为供给量，费用为0

AC代码：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <string>
    #include <map>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int inf = 0x3f3f3f3f;
    const int N = 220;
    struct Node
    {
        int from,to,cap,flow,cost;
    };
    vector<Node> e;
    vector<int> v[N];
    int vis[N],dis[N];
    int p[N],a[N];  //p保存father，a保存cap
    void Clear(int x)
    {
        for(int i=0;i<=x;i++)
            v[i].clear();
        e.clear();
    }
    void add_Node(int from,int to,int cap,int cost)
    {
        e.push_back((Node){from,to,cap,0,cost});
        e.push_back((Node){to,from,0,0,-cost});
        int len = e.size()-1;
        v[to].push_back(len);
        v[from].push_back(len-1);
    }
    bool BellmanFord(int s,int t,int& flow,int& cost)
    {
        Del(dis,inf);
        Del(vis,0);
        dis[s] = 0;
        vis[s] = 1;
        p[s] = 0;
        a[s] = inf;
        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(int i=0; i<v[u].size(); i++)
            {
                Node& g = e[v[u][i]];
                if(g.cap>g.flow && dis[g.to] > dis[u]+g.cost)
                {
                    dis[g.to] = dis[u] + g.cost;
                    p[g.to] = v[u][i];  //保存前驱
                    a[g.to] = min(a[u],g.cap-g.flow);
                    if(!vis[g.to])
                    {
                        q.push(g.to);
                        vis[g.to]=1;
                    }
    
                }
            }
        }
        if(dis[t] == inf)
            return false;
        flow += a[t];
        cost += dis[t]*a[t];
        int u = t;
        while(u!=s)
        {
            e[p[u]].flow += a[t];
            e[p[u]^1].flow -= a[t];
            u = e[p[u]].from;
        }
        return true;
    }
    int Min_Cost(int s,int t)
    {
        int flow=0,cost = 0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }
    int need[N][N];
    int sup[N][N];
    int r[N];
    int main()
    {
        int n,m,k;  //n 店主 k 物品 M 供应商
        while(~scanf("%d%d%d",&n,&m,&k) && (m+n+k))  //记得啊
        {
            int s = 0;
            for(int i=1;i<=n;i++)
            {
                for(int wu = 1;wu<=k;wu++)
                {
                    scanf("%d",&need[i][wu]);
                }
            }
            Del(r,0);
            for(int i=1;i<=m;i++)
                for(int j=1;j<=k;j++){
                    scanf("%d",&sup[i][j]); //第i个供应商供应第j个物品的个数
                    r[j]+=sup[i][j];
                }
            int ans = 0,ok=1;
            for(int wu = 1; wu<= k;wu++)
            {
                int s = 0 ,t= n+m+1;
                int tmp = 0;
                for(int i=1;i<=n;i++)
                {
                    add_Node(s,i,need[i][wu],0);
                    tmp+=need[i][wu];
                }
                if(tmp>r[wu])
                    ok=0;
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=m;j++)
                    {
                        int x;scanf("%d",&x);
                        add_Node(i,n+j,inf,x);
                    }
                }
                for(int i=1;i<=m;i++)
                    add_Node(n+i,t,sup[i][wu],0);
                if(ok)
                    ans+=Min_Cost(s,t);
                Clear(t);
            }
            if(ok==0)
                puts("-1");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

[poj 2516 Minimum Cost]: http://poj.org/problem?id=2516