标签：

「AHOI2014/JSOI2014」支线剧情

传送门
上下界网络流。
以 \(1\) 号节点为源点 \(s\) ，新建一个汇点 \(t\)，，如果 \(u\) 能到 \(v\)，那么连边 \(u \to v\)，下界为 \(1\)，上界为 \(+\infty\)，用度为对应的所需时间，暗示这段剧情至少看一次，且看一次价钱为对应的所需时间。
又因为我们可以在任何一个节点重开一次，所以我们的每个节点 \(u\) 都连边 \(u \to t\) ，下界为 \(0\)，上界为 \(+\infty\)，用度也是 \(0\)。
然后我们就对建出来的网络跑一个有源汇有上下界可行流即可。
注意最后算答案的时候还要把每条边至少走一次的价钱算进来。
参考代码：

#include <cstring> #include <cstdio> #include <queue> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 310, __ = 1e5 + 10, INF = 2147483647; int tot = 1, head[_]; struct Edge { int ver, cap, cst, nxt; } edge[__ << 1]; inline void Add_edge(int u, int v, int d, int cs) { edge[++tot] = (Edge) { v, d, cs, head[u] }, head[u] = tot; } inline void link(int u, int v, int d, int cs) { Add_edge(u, v, d, cs), Add_edge(v, u, 0, -cs); } int n, s, t, S, T, d[_], pre[_], dis[_], exi[_]; inline void Link(int u, int v, int l, int r, int cs) { link(u, v, r - l, cs), d[u] -= l, d[v] += l; } inline int spfa() { memset(dis + 1, 0x3f, sizeof (int) * T); memset(pre + 1, 0, sizeof (int) * T); queue < int > Q; Q.push(S), dis[S] = 0, exi[S] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(), exi[u] = 0; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].ver; if (dis[v] > dis[u] + edge[i].cst && edge[i].cap > 0) { dis[v] = dis[u] + edge[i].cst, pre[v] = i; if (!exi[v]) exi[v] = 1, Q.push(v); } } } return pre[T] != 0; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), s = 1, t = n + 1, S = n + 2, T = n + 3; int ans = 0; for (rg int k, x, y, i = 1; i <= n; ++i) { read(k); while (k--) read(x), read(y), Link(i, x, 1, INF, y), ans += y; } for (rg int i = 1; i <= n; ++i) Link(i, t, 0, INF, 0); link(t, s, INF, 0); for (rg int i = s; i <= t; ++i) { if (d[i] > 0) link(S, i, d[i], 0); if (d[i] < 0) link(i, T, -d[i], 0); } while (spfa()) { int flow = INF; for (rg int i = pre[T]; i; i = pre[edge[i ^ 1].ver]) flow = min(flow, edge[i].cap); for (rg int i = pre[T]; i; i = pre[edge[i ^ 1].ver]) edge[i].cap -= flow, edge[i ^ 1].cap += flow; ans += dis[T] * flow; } printf("%d\n", ans); return 0; }

「AHOI2014/JSOI2014」支线剧情