[AHOI2014/JSOI2014]支線劇情

有n個劇情點，對于第i個劇情點有ki個分支，分別通往tij劇情點，耗費時間為bij。從1號點開始，可以從任何節點返回1號點，要遍歷所有的邊的最少耗費時間為多少

上下界網絡流板子題，每一條邊的下界為1，除了起點外每一個點都可以是終點，所以建第n+1個點為匯點，這樣就是一個有源有匯的上下界網絡流，由匯點向源點建一條容量為inf的邊。這個題沒有上界，所以一定可以保證有可行流。

初始每條邊都默認flow為1，先加入答案，然后建立平衡網絡，跑出可行流加入答案即可。

//remember to delete freopen #include <bits/stdc++.h> using namespace std;//faster_reader inline int read () {int f = 1, a = 0;char c = getchar ();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar ();}while (c >= '0' && c <= '9'){a = a * 10 + c - '0';c = getchar ();}return f * a; }const int N = 3100, M = 100010; const int inf = 1e9 + 7; long long ans = 0; int head[N], now[N], num = -1; int in[N], out[N], dis[N]; bool vis[N]; int s, t, n;struct edge {int nxt, to, flow, pri; }; edge e[M];void addEdge(int x, int y, int z, int w) {e[++ num].nxt = head[x];head[x] = num;e[num].to = y;e[num].flow = z;e[num].pri = w; }bool spfa() {for (int i = 0; i <= n + 2; i ++)dis[i] = inf;dis[s] = 0;queue <int> q;q.push(s);while (!q.empty()){int x = q.front(); q.pop();for (int i = head[x]; i != -1; i = e[i].nxt){int to = e[i].to;if (dis[to] > dis[x] + e[i].pri && e[i].flow > 0){dis[to] = dis[x] + e[i].pri;q.push(to);}}}if (dis[t] != inf) return true;return false; }int dfs(int x, int flow) {if (vis[x]) return 0;vis[x] = 1;if (x == t)return flow;for (int i = now[x]; i != -1; i = e[i].nxt){now[x] = i;int to = e[i].to;if (dis[to] == dis[x] + e[i].pri && e[i].flow > 0){int val = dfs(to, min(flow, e[i].flow));if (val > 0){e[i].flow -= val;e[i ^ 1].flow += val;ans += val * e[i].pri;return val;}}}return 0; }void dinic(int x, int y) {s = x; t = y;while (spfa()){for (int i = 0; i <= n + 2; i ++){now[i] = head[i];vis[i] = 0;}int val;while (val = dfs (s, inf)){if (val == 0)break;}} }int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);n = read();memset (head, -1, sizeof (head));for (int i = 1; i <= n; i ++){int k = read();out[i] = k;for (int j = 1; j <= k; j ++){int tt, bb;tt = read(); bb = read();in[tt] ++;ans += bb;addEdge(i, tt, inf, bb);addEdge(tt, i, 0, -bb);}if (i > 1){addEdge(i, n + 1, inf, 0);addEdge(n + 1, i, 0, 0);}}addEdge(n + 1, 1, inf, 0);addEdge(1, n + 1, 0, 0);for (int i = 1; i <= n; i ++){if (in[i] > out[i]){addEdge (0, i, in[i] - out[i], 0);addEdge (i, 0, 0, 0);}if (in[i] < out[i]){addEdge (i, n + 2, out[i] - in[i], 0);addEdge (n + 2, i, 0, 0);}}s = 0; t = n + 2;dinic(0, n + 2);cout << ans;return 0; }

總結

以上是生活随笔為你收集整理的[AHOI2014/JSOI2014]支线剧情的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。