HDU 6118 度度熊的交易计划 （裸最小费用流）

度度熊的交易计划

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1074    Accepted Submission(s): 389

Problem 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
        

Source 2017"百度之星"程序设计大赛 - 初赛（B）  

Recommend liuyiding   |   We have carefully selected several similar problems for you:   6132  6131  6130  6129  6128   

思路：

最最最裸的最小费用流把，注意是最小费用流， 这题不比要求最大流，只要费用最高就好了， 那么就把spfa里改成 if(dis[t] > 0) return 0; else return 1;就好了...

①建立源点，连入各个节点，花费为-c【i】，流为d【i】。 （如果是最小利益，就要正常建， 花费是负的，收益是正的）

②建立汇点，将各个节点连入汇点，花费为a【i】，流为b【i】。

③将图的边（u，v）加到网络中，花费为w，流为INF。

然后连续最短路跑费用流就行了，值得注意的一个坑点是，我们如果从源点到汇点的距离大于0的时候，我们这条边如果走过去了就相当于赔钱了。

所以当dis【tt】>0的时候，我们终止跑费用流。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 5e2 + 7;
const int maxe = 200005;
const int INF = 0x3f3f3f3f;
int head[maxe], dis[maxn], path[maxn], pre[maxn], book[maxn] , n, m, s, t, k, sum;
struct node
{
    int v, w, f, next, cnt;
}edge[maxe];
void addEdge(int u, int v, int f, int w)
{
    edge[k].v = v;
    edge[k].w = w;
    edge[k].f = f;
    edge[k].cnt = k;
    edge[k].next = head[u];
    head[u] = k++;
    edge[k].v = u;
    edge[k].w = -w;
    edge[k].f = 0;
    edge[k].cnt = k;
    edge[k].next = head[v];
    head[v] = k++;
}
void init()
{
    s = 0, t = n+1, k = 0;
    memset(head, -1, sizeof(head));
}
int spfa()
{
    queue<int> q;
    q.push(s);
    memset(pre, -1, sizeof(pre));
    memset(path, -1, sizeof(path));
    for(int i = 1; i <= t; i++) dis[i] = INF;
    dis[s] = 0;
    memset(book, 0, sizeof(book));
    book[s] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        book[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int to = edge[i].v;
            int w = edge[i].w;
            int f = edge[i].f;
            if(f && dis[to] > dis[u] + w)
            {
                dis[to] = dis[u] + w;
                pre[to] = u;
                path[to] = edge[i].cnt;
                if(!book[to])
                {
                    q.push(to);
                    book[to] = 1;
                }
            }
        }
    }
    if(dis[t] > 0) return 0;
    else return 1;
}
int Min_costflow()
{
    int ans = 0;
    int maxflow = 0;
    while(spfa())
    {
        int minx = INF;
        for(int i = t; i != s; i = pre[i])
        {
            minx = min(minx, edge[path[i]].f);
        }
        maxflow += minx;
        ans += dis[t]*minx;
        for(int i = t; i != s; i = pre[i])
        {
            edge[path[i]].f -= minx;
            edge[path[i]^1].f += minx;
        }
    }
    return ans;
}
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init();
        int a, b, c, d;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            addEdge(s, i, b, a);
            addEdge(i, t, d, -c);
        }
        for(int i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            if(a == b) continue;
            addEdge(a, b, INF, c);
            addEdge(b, a, INF, c);
        }
        printf("%d\n", -Min_costflow());
    }
    return 0;
}