[HDU 6118][百度之星 2017 初赛 B] 度度熊的交易计划

题目大意

在一张 \(n\) 个点 \(m\) 条边的无向图上,每个点可以以 \(a_i\) 的成本制造至多 \(b_i\) 个商品,也可以以 \(c_i\) 的价格售出至多 \(d_i\) 个商品,每条边可以以每件商品 \(k_i\) 的价格运输商品。求最大利润。

多组数据。

\(1 \leq n \leq 500\)

\(1 \leq m \leq 1,000\)

\(1 \leq a_i, b_i, c_i, d_i, k_i \leq 1,000\)

题目链接

HDU 6118

题解

考虑费用流,建立一个源点和一个汇点,从源点向每个点建一条容量为 \(b_i\)、费用为 \(a_i\) 的边,从每个点向汇点建一条容量为 \(d_i\)、费用为 \(-c_i\) 的边,对于原图中边权为 \(k\) 的每一条边,建一条对应的容量无限、费用为 \(k\) 的双向边,跑最小费用可行流,答案即最小费用的相反数。

代码

与最小费用最大流的区别用注释表示了。

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
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 505;

struct Edge;
struct Node;

struct Node {
std::vector<Edge> e;
Edge *pre;
int flow, dist, cnt;
bool inq;
} N[MAXN];

struct Edge {
Node *u, *v;
int cap, flow, cost, rev;

Edge(Node *u, Node *v, int cap, int cost, int rev) : u(u), v(v), rev(rev), cap(cap), flow(0), cost(cost) {}
};

void addEdge(int u, int v, int cap, int cost) {
N[u].e.push_back(Edge(&N[u], &N[v], cap, cost, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, -cost, N[u].e.size() - 1));
}

namespace EdmondsKarp {
void solve(int s, int t, int n, int &flow, int &cost) {
flow = cost = 0;
while (true) {
for (int i = 0; i < n; i++) {
N[i].dist = INT_MAX;
N[i].flow = 0;
N[i].pre = NULL;
}

std::queue<Node *> q;
q.push(&N[s]);
N[s].dist = 0;
N[s].flow = INT_MAX;
while (!q.empty()) {
Node *u = q.front();
q.pop();

for (Edge *e = &u->e.front(); e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->dist > u->dist + e->cost) {
e->v->dist = u->dist + e->cost;
e->v->flow = std::min(u->flow, e->cap - e->flow);
e->v->pre = e;
q.push(e->v);
}
}
}

// if (N[t].dist == INT_MAX) break;
if (N[t].dist > 0) break;

for (Edge *e = N[t].pre; e; e = e->u->pre) {
e->flow += N[t].flow;
e->v->e[e->rev].flow -= N[t].flow;
}

flow += N[t].flow;
cost += N[t].dist * N[t].flow;
}
}
}

void init(int n) {
for (int i = 0; i < n; i++) {
N[i].e.clear();
}
}

int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
init(n + 2);
const int s = 0, t = n + 1;

for (int i = 1, a, b, c, d; 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 = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, INT_MAX, w);
addEdge(v, u, INT_MAX, w);
}

int flow, cost;
EdmondsKarp::solve(s, t, n + 2, flow, cost);
printf("%d\n", -cost);
}

return 0;
}