「AHOI2014/JSOI2014」支线剧情

「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;

}