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

描述

传送门:2017"百度之星"程序设计大赛 - 初赛(B)

度度熊参与了喵哈哈村的商业大会,但是这次商业大会遇到了一个难题:
喵哈哈村以及周围的村庄可以看做是一共由$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

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

Sample Output

1
23

思路

  • 首先建立超级源点 $s$ ,与超级汇点 $t$ 。
  • 因为生产一个商品需要花费 $a[i]$ 元,且上限为 $b[i]$ ,所以我们从 $s$ 向这些点之间连一条容量为 $b[i]$ ,费用为 $a[i]$ 的边。
  • 同样的道理,出售一个商品可以赚到 $c[i]$ 元,最多出售 $d[i]$ 个,于是我们从这些点向 $t$ 连一条容量为 $d[i]$ ,费用为 $-c[i]$ 的边。
  • 最后所有的公路也是花费,从 $u$ 到 $v$ 连接一条双向边,容量为 $+∞$ ,费用为 $k$ ,然后跑一边最小费用流即可。
  • 需要注意的一点是:我们如果从源点到汇点的距离大于$0$的时候,我们这条边如果走过去了就相当于赔钱了,这时候就应该停止跑费用流。
  • 最后答案取相反数即为最多可赚的钱。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1e3 + 5;
struct Edge
{
int from, to, cap, flow, cost;
Edge(int u, int v, int c, int f, int w): from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct MCMF
{
int n, m;
vector <Edge> edges;
vector <int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];

void init(int n)
{
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}

void AddEdge(int from, int to, int cap, int cost)
{
edges.pb(Edge(from, to, cap, 0, cost));
edges.pb(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].pb(m - 2);
G[to].pb(m - 1);
}

bool BellmanFord(int s, int t, int &flow, ll& cost)
{
clr(d, 0x3f);
clr(inq, 0);
d[s] = 0;
inq[s] = 1;
p[s] = 0;
a[s] = INF;
queue <int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i++)
{
Edge &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] = 1;
}
}
}
}
if (d[t] > 0) return false; // 赔钱
flow += a[t];
cost += (ll) d[t] * (ll) a[t];
for (int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
return true;
}
int MinCostMaxFlow(int s, int t, ll& cost)
{
int flow = 0;
cost = 0;
while (BellmanFord(s, t, flow, cost));
return flow;
}
};

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m, a, b, c, d;
while (~scanf("%d%d", &n, &m))
{
int S = 0, T = n + 1;
MCMF ans;
ans.init(n + 2);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
ans.AddEdge(S, i, b, a);
ans.AddEdge(i, T, d, -c);
}
while (m--)
{
scanf("%d%d%d", &a, &b, &c);
ans.AddEdge(a, b, INF, c);
ans.AddEdge(b, a, INF, c);
}
ll cost;
ans.MinCostMaxFlow(S, T, cost);
printf("%lld\n", -cost);
}
return 0;
}
捐助作者