Minimum Cost POJ - 2516（模板题。。没啥好说的。。）

题意：

从发货地到商家送货求送货花费的最小费用。。。

有m个发货地，，，n个商家，，每个商家所需要的物品和物品的个数都不一样，，，每个发货地有的物品和物品的个数也不一样，，，

从不同的发货地到不同的商家送不同的物品所花费的价钱也不一样。。

解析；

建立超级源s和超级汇t

因为每个商家所需的每个物品的数量都不一样，，，所以我们要分物品来进行最小费用最大流

在最外面一个循环，遍历每一个物品，，，然后对于当前物品建图

把每个发货地和s连边权值为每个发货地所拥有的当前物品的数量，，，花费0

把商家个t连边，，权值为每个商家所需要的当前物品的数量，，花费0

然后发货地和商家连边。。。权值为INF，花费为每个发货地到每个商家对于当前物品所对应的花费

这是一个对象所需不同物品的个数不一样的题

贴一个对象所需不同物品的个数一样的题：https://www.cnblogs.com/WTSRUVF/p/9202751.html

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

typedef long long LL;

int head[maxn], d[maxn], vis[maxn], p[maxn], f[maxn];

int frome[maxn], to[maxn], ca[][][];

int needs[][], have[][];

int n, m, s, t, k;

int cnt, flow, value;

struct node{

    int u, v, c, w, next;

}Node[maxn];

void add_(int u, int v, int c, int w)

{

    Node[cnt].u = u;

    Node[cnt].v = v;

    Node[cnt].c = c;

    Node[cnt].w = w;

    Node[cnt].next = head[u];

    head[u] = cnt++;

}

void add(int u, int v, int c, int w)

{

    add_(u, v, c, w);

    add_(v, u,  ,-w);

}

int spfa()

{

    queue<int> Q;

    for(int i=; i<maxn; i++) d[i] = INF;

    mem(vis, );

    mem(p, -);

    Q.push(s);

    d[s] = ;

    vis[s] = ;

    p[s] = ; f[s] = INF;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        vis[u] = ;

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] > d[e.u] + e.w && e.c > )

            {

                d[e.v] = d[e.u] + e.w;

                p[e.v] = i;

                f[e.v] = min(f[u], e.c);

                if(!vis[e.v])

                {

                    Q.push(e.v);

                    vis[e.v] = ;

                }

            }

        }

    }

    if(p[t] == -) return ;

    flow += f[t]; value +=  f[t]* d[t];

    for(int i=t; i!=s; i=Node[p[i]].u)

    {

        Node[p[i]].c -= f[t];

        Node[p[i]^].c += f[t];

    }

    return ;

}

int max_flow()

{

    value = ;

    flow = ;

    while(spfa());

    return value;

}

int main()

{

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

    {

        int ret = ;

        int ok = ;

        s = , t = (n+m)*+;

        mem(head, -);

        mem(frome, );

        mem(to, );

        cnt = ;

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

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

            {

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

                frome[j] += needs[i][j];

            }

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

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

            {

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

                to[j] += have[i][j];

            }

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

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

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

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

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

        {

            if(frome[i] > to[i])

            {

                printf("-1\n");

                ok = ;

                break;

            }

        }

        if(!ok) continue;

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

        {

            mem(head, -);

            cnt = ;

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

                add(j, t, needs[j][i], );

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

                add(s, n+j, have[j][i], );

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

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

                    add(n+j, l, INF, ca[i][l][j]);

            ret += max_flow();

        }

        cout<< ret <<endl;

    }

    return ;

}

巴特西

Minimum Cost POJ - 2516（模板题。。没啥好说的。。）

最新文章

热门文章