[AHOI 2014] 支线剧情

题目大意

考虑一个 DAG ,每条边有边权,同时从任意一个点可以不花费代价地回到起点,求遍历完整个 DAG 的代价(每条边每跑一次就记一次代价)。

1n3001 \leqslant n \leqslant 300

0ki50,  0ki5,0000 \leqslant k_i \leqslant 50, \; 0 \leqslant \sum k_i \leqslant 5,000 (每个顶点的子节点数)

1ti,j3001 \leqslant t_{i, j} \leqslant 300 (边权)

题目链接

【AHOI 2014】支线剧情 - LibreOJ 2226

题解

仙剑系列算是我的童年吧。。。

上下界费用流。

把整个 DAG 建成求费用流的图,对于原来的边 (u,v,w)(u, v, w) ,改建为 (u,v,[1,+],w)(u, v, [1, +\infty], w)

对于容量上下界的处理,从源点向边指向的点连容量为下界、费用为 ww 的边,保证指向的点收到了下界的流量;从边的起点向汇点连容量为下界、费用为 00 的边,保证起点有下界的流量流出;原来的边的容量改为 上界 - 下界。

需要静态分配内存(费用流好慢。。。)。

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
#include <new>
const int MAXN = 305;
const int MAXK = 5005;
struct Edge;
struct Node {
Edge *e, *pre;
int dist, flow;
bool inq;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next, *rev;
int cap, flow, cost;
Edge() {}
Edge(Node *u, Node *v, int cap, int cost) : u(u), v(v), next(u->e), cap(cap), flow(0), cost(cost) {}
} _pool[(MAXK + MAXN) << 2], *_cur = _pool;
void addEdge(int u, int v, int cap, int cost){
N[u].e = new (_cur++) Edge(&N[u], &N[v], cap, cost);
N[v].e = new (_cur++) Edge(&N[v], &N[u], 0, -cost);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
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].inq = false;
N[i].pre = NULL;
N[i].flow = 0;
N[i].dist = INT_MAX;
}
std::queue<Node *> q;
N[s].flow = INT_MAX;
N[s].dist = 0;
q.push(&N[s]);
while (!q.empty()) {
Node *u = q.front();
q.pop();
u->inq = false;
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->dist > u->dist + e->cost) {
e->v->dist = u->dist + e->cost;
e->v->pre = e;
e->v->flow = std::min(u->flow, e->cap - e->flow);
if (!e->v->inq) {
e->v->inq = true;
q.push(e->v);
}
}
}
}
if (N[t].dist == INT_MAX) break;
for (Edge *e = N[t].pre; e; e = e->u->pre) {
e->flow += N[t].flow;
e->rev->flow -= N[t].flow;
}
flow += N[t].flow;
cost += N[t].flow * N[t].dist;
}
}
}
int main() {
int n;
scanf("%d", &n);
const int s = 0, t = n + 1;
for (int i = 1; i <= n; i++) {
int k;
scanf("%d", &k);
for (int j = 0; j < k; j++) {
int v, w;
scanf("%d %d", &v, &w);
addEdge(i, v, INT_MAX, w);
addEdge(s, v, 1, w);
}
if (k) addEdge(i, t, k, 0);
if (i != 1) addEdge(i, 1, INT_MAX, 0);
}
int flow, cost;
EdmondsKarp::solve(s, t, n + 2, flow, cost);
printf("%d\n", cost);
return 0;
}