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

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 15 5 6 13 5 7 71 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]​​ 的边。

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

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

AC 代码

#includeusing namespace std;#define INF 0x3f3f3f3ftypedef 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; queueq; 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。