HDU 6118 度度熊的交易计划 (最小费用最大流)

Description

度度熊参与了喵哈哈村的商业大会,但是这次商业大会遇到了一个难题:

喵哈哈村以及周围的村庄可以看做是一共由 n 个片区, m 条公路组成的地区。

由于生产能力的区别,第 i 个片区能够花费 a[i] 元生产 1 个商品,但是最多生产 b[i] 个。

同样的,由于每个片区的购买能力的区别,第 i 个片区也能够以 c[i] 的价格出售最多 d[i] 个物品。

由于这些因素,度度熊觉得只有合理的调动物品,才能获得最大的利益。

据测算,每一个商品运输 1 公里,将会花费 1 元。

那么喵哈哈村最多能够实现多少盈利呢?

 

Input

本题包含若干组测试数据。

每组测试数据包含:

第一行两个整数 n,m 表示喵哈哈村由 n 个片区、 m 条街道。

接下来 n 行,每行四个整数 a[i],b[i],c[i],d[i] 表示的第 i 个地区,能够以 a[i] 的价格生产,最多生产 b[i] 个,以 c[i] 的价格出售,最多出售 d[i] 个。

接下来 m 行,每行三个整数, u[i],v[i],k[i] ,表示该条公路连接 u[i],v[i] 两个片区,距离为 k[i]

可能存在重边,也可能存在自环。

满足:

1<=n<=500,

1<=m<=1000,

1<=a[i],b[i],c[i],d[i],k[i]<=1000,

1<=u[i],v[i]<=n

 

Output

输出最多能赚多少钱。

 

Sample Input

2 1
5 5 6 1
3 5 7 7
1 2 1

 

Sample Output

23

 

思路

最小费用最大流,首先建立超级源点 s ,与超级汇点 t

因为生产一个商品需要花费 a[i] 元,且上限为 b[i] ,所以我们从 s 向这些点之间连一条容量为 b[i] ,费用为 -a[i] 的边。

同样的道理,出售一个商品可以赚到 c[i] 元,最多出售 d[i] 个,于是我们从这些点向 t 连一条容量为 d[i] ,费用为 c[i] 的边。

最后所有的公路也是花费,从 uv 连接一条双向边,容量为 INF ,费用为 -k ,然后跑一边模板即可。

注意:图中存在自环,当我们得到两点路径长度小于 0 时应终止计算。

 

AC 代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

typedef long long LL;

const int M=2010;
const int N=510;

struct edge
{
    int to;
    int next;
    int cap;
    int cost;
} e[11000];

int head[N],tot;
int d[N], pre[N], path[N];
bool vis[N];

void init()
{
    memset(head,-1,sizeof(head));
    tot = 0;
}

void addedge(int s, int t, int cap, int cost)
{
    e[tot].to=t;
    e[tot].cap=cap;
    e[tot].cost=cost;
    e[tot].next=head[s];
    head[s] = tot++;
    e[tot].to=s;
    e[tot].cap=0;
    e[tot].cost=-cost;
    e[tot].next=head[t];
    head[t] = tot++;
}

int spfa(int s, int t)
{
    memset(d,-INF,sizeof(d));
    memset(pre,-1,sizeof(pre));
    memset(path,-1,sizeof(path));
    memset(vis,false,sizeof(vis));
    int res = d[0];
    d[s] = 0;
    vis[s] = true;
    queue<int>q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = e[i].next)
        {
            int v = e[i].to;
            if (d[v] < d[u] + e[i].cost && e[i].cap > 0)
            {
                d[v] = d[u] + e[i].cost;
                pre[v] = u;
                path[v] = i;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return d[t] != res;
}

int MinCostMaxFlow(int s, int t,int &cost)
{
    int flow;
    flow=cost=0;
    while (spfa(s, t))
    {
        int minn = INF;
        for (int i = t; i != s && ~i; i = pre[i])
            minn = min(minn, e[path[i]].cap);
        for (int i = t; i != s && ~i; i = pre[i])
        {
            e[path[i]].cap -= minn;
            e[path[i] ^ 1].cap += minn;
        }
        if (d[t] < 0)
            break;
        flow += minn;
        cost += minn * d[t];
    }
    return flow;
}

int main(void)
{
    int n,m;
    while (cin>>n>>m)
    {
        init();
        int s=0,t=n+1,cost;
        for (int i=1; i<=n; i++)
        {
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            addedge(s,i,b,-a);
            addedge(i,t,d,c);
        }
        while (m--)
        {
            int u,v,k;
            cin>>u>>v>>k;
            addedge(u,v,INF,-k);
            addedge(v,u,INF,-k);
        }
        MinCostMaxFlow(s,t,cost);
        cout<<cost<<endl;
    }
    return 0;
}