HDU 6118 2017百度之星初赛B 度度熊的交易计划（费用流）

时间：2024-04-30 17:35:56

度度熊的交易计划

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 254    Accepted Submission(s): 80

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

【分析】费用流模板题。不过在

BellmanFord函数里面加一句话
if(d[t]<0) return false;
保证跑最大流的时候不会亏本。
#include <bits/stdc++.h>

#define rep(i,a,n) for (int i=a;i<=n;i++)

#define per(i,a,n) for (int i=n;i>=a;i--)

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

#define SZ(x) ((int)(x).size())

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

using namespace std;

typedef vector<int> vi;

typedef long long ll;

typedef pair<int,int> pii;

const ll mod=;

const int inf=(<<);

const double pi=acos(-);

ll powmod(ll a,ll b) {ll res=;a%=mod; assert(b>=); for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}

inline void pcas(int ca) {printf("Case %d: ",ca);}

int n,m;

const int maxn=+;

struct Edge {

  int from, to, cap, flow;

  int  cost;

};

inline int Min(int aa,int bb)

{

    return aa<bb?aa:bb;

}

struct MCMF {

  int n, m, s, t;

  vector<Edge> edges;

  vector<int> G[maxn];

  int inq[maxn];         // 是否在队列中

  int d[maxn];           // Bellman-Ford

  int p[maxn];           // 上一条弧

  int a[maxn];           // 可改进量

  void init(int n) {

    this->n = n;

    for(int i = ; i < n; i++) G[i].clear();

    edges.clear();

  }

  void AddEdge(int from, int to, int cap, int cost) {

    edges.push_back((Edge){from, to, cap, , cost});

    edges.push_back((Edge){to, from, , , -cost});

    m = edges.size();

    G[from].push_back(m-);

    G[to].push_back(m-);

  }

  bool BellmanFord(int s, int t, int& flow,int& cost) {

    for(int i = ; i < n; i++) d[i] = -;

    memset(inq, , sizeof(inq));

    d[s] = ; inq[s] = ; p[s] = ; a[s] = inf;

    queue<int> Q;

    Edge e;

    int l,u;

    Q.push(s);

    while(!Q.empty()) {

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

      inq[u] = ;

      l=G[u].size();

      for(int i = ; i < l; i++) {

        e = edges[G[u][i]];

        if(e.cap > e.flow && d[e.to]<d[u] + e.cost) {

          d[e.to] = d[u] + e.cost;

          p[e.to] = G[u][i];

          a[e.to] = Min(a[u], e.cap - e.flow);

          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = ; }

        }

      }

    }

    if(d[t]<) return false;

    cost += d[t]*a[t];

    u = t;

    while(u != s) {

      edges[p[u]].flow += a[t];

      edges[p[u]^].flow -= a[t];

      u = edges[p[u]].from;

    }

    return true;

  }

  // 需要保证初始网络中没有负权圈

    int Mincost(int s, int t) {

        int cost = ;

        int flow=;

        while(BellmanFord(s, t,flow, cost));

        return cost;

    }

};

int a[maxn],b[maxn],c[maxn],d[maxn];

MCMF ac;

int main()

{

    int n,m;

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

        int a,b,c,d;

        ac.init(n+);

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

            scanf("%d%d%d%d",&a,&b,&c,&d);

            ac.AddEdge(,i,b,-a);

            ac.AddEdge(i,n+,d,c);

        }

        while (m--) {

            scanf("%d%d%d",&a,&b,&c);

            ac.AddEdge(a,b,inf,-c);

            ac.AddEdge(b,a,inf,-c);

        }

        printf("%d\n",ac.Mincost(,n+));

    }

    return ;

}

相关文章