poj 2516 Minimum Cost 【最小费用最大流】-蒲公英云

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

题目：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;
}