菜哭武的面试题(最小费用最大流)

描述

传送门:2018年“新格尔杯”第十五届同济大学程序设计竞赛 暨上海邀请赛 - Problem B

新格尔公司的天才程序员菜哭武最近在担任面试官,他今天出了这样一个题目。给出一个长度为N的整数序列$h_i$,现在要通过一些操作将这个序列修改为单调不降序列,即$h_i ≤ h_{i+1}$。可以用的操作有$M$种,第$i$种操作可以通过支付$c_i$的代价将一段长度恰为$l_i$的连续子序列$+1$或$-1$(由对应的操作符确定是$+1$还是$-1$,具体参考输入格式)。

不限制每种操作的使用次数,序列中的hi可以被改为任意整数(可以是负数),求最小代价,无解输出$-1$。

输入

第一行一个整数$T$,表示有$T$组测试数据。($1 ≤ T ≤ 4$)
然后每组有$M+2$行:
第一行,两个整数$N$,$M$; ($N,M ≤ 200$)
第二行,$N$个整数$h_i$($h_i ≤ 10^6$)
接下来$m$行,每行格式为$op_i, l_i, c_i$空格隔开,其中$op_i$为一个字符,表示这种操作是$+1$ 还是$-1$。($l_i ≤ N$, $1 ≤ c_i ≤ 10^6$)

输出

对于每组数据,第一行输出Case #x: ($x$编号从1开始)
第二行是一个整数,代表最小代价,若无解输出$-1$。

样例输入

1
2
3
4
5
6
7
8
2
3 2
3 2 1
+ 1 1
- 1 1
3 1
3 2 1
+ 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
1
10 10
23 1 8 14 2 3 15 50 53 53
+ 4 6
- 1 10
+ 2 4
+ 4 2
- 3 5
+ 1 2
+ 3 2
+ 5 7
- 1 6
+ 4 5

样例输出

1
2
3
4
Case #1:
2
Case #2:
-1
1
2
Case #1:
96

思路

  • 转化为差分之后目标是让 $a_2$ 到 $a_n$ 都非负。
  • 建图如下:
    • 让$S$连大于零的点(意味着可以送出东西);让小于零的连$T$(意味着要加东西),容量分别为绝对值。
    • 每一个给出的操作都是一条边,容量无限,费用就是输入的$c$。
    • $S$ 连$a_1$ 和 $a_{n+1}$ ,容量无限。
    • 目标是让所有连 $T$ 的东西都满载(收东西的地方填满)。
  • 跑最小费用最大流即可。

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#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 = 1 << 8;
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]; //bellmanford
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)
{
for (int i = 0; i < n; i++) d[i] = INF;
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] == INF) 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;
}
} gao;

int a[maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T, kase = 0;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = n; i; i--) a[i] -= a[i - 1];
gao.init(n + 3);
int s = 0, t = n + 2;
int tot = 0;
for (int i = 2; i <= n; i++)
{
if (a[i] > 0) gao.AddEdge(s, i, a[i], 0);
if (a[i] < 0) gao.AddEdge(i, t, -a[i], 0), tot -= a[i];
}
gao.AddEdge(s, 1, INF, 0);
gao.AddEdge(s, n + 1, INF, 0);
while (m--)
{
static char op;
static int l, c;
scanf(" %c%d%d", &op, &l, &c);
if (op == '-')
for (int i = 1; i + l <= n + 1; i++)
gao.AddEdge(i, i + l, INF, c);
else
for (int i = 1; i + l <= n + 1; i++)
gao.AddEdge(i + l, i, INF, c);
}
ll cost;
int flow = gao.MincostMaxflow(s, t, cost);
printf("Case #%d:\n", ++kase);
if (flow == tot)
printf("%lld\n", cost);
else
puts("-1");
}
return 0;
}
捐助作者
0%