arc tdi span return || ostream status ons
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1686 Solved: 1031
所以 JYY 要想回到之前的剧情点,唯一的方法就是退出当前游戏,并开始新的游戏,也就是回到 1 号剧情点。JYY 可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦,JYY 希望花费最少的时间,看完所有不同的支线剧情。
JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 1 号剧情点,也就是游戏的开始。显然任何一个剧情点都是从 1 号剧情点可达的。此外,随着游戏的进行,剧情是不可逆的。所以游戏保证从任意剧情点出发,都不能再回到这个剧情点。由于 JYY 过度使用修改器,导致游戏的 "存档" 和 "读档" 功能损坏了,
JYY 现在所玩的 RPG 游戏中,一共有 N 个剧情点,由 1 到 N 编号,第 i 个剧情点可以根据 JYY 的不同的选择,而经过不同的支线剧情,前往 Ki 种不同的新的剧情点。当然如果为 0,则说明 i 号剧情点是游戏的一个结局了。
【问题描述】
都有很多的支线剧情,现在 JYY 想花费最少的时间看完所有的支线剧情。
宅男 JYY 非常喜欢玩 RPG 游戏,比如仙剑,轩辕剑等等。不过 JYY 喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往
【故事背景】
情点,并且观看这段支线剧情需要花费的时间。
第一个整数为,接下来个整数对,Bij 和 Tij,表示从剧情点 i 可以前往剧
接下来 N 行,第 i 行为 i 号剧情点的信息;
输入一行包含一个正整数 N。
输出一行包含一个整数,表示 JYY 看完所有支线剧情所需要的最少时间。
JYY 需要重新开始 3 次游戏,加上一开始的一次游戏,4 次游戏的进程是
对于 100% 的数据满足 N<=300,0<=Ki<=50,1<=Tij<=300,Sigma(Ki)<=5000
1->2->4,1->2->5,1->3->5 和 1->3->6。
By 佚名上传
图论 网络流 有下界的费用流
我们愉快地发现这是一个 DAG,那么就可以愉快地跑网络流。
每个支线剧情(即每条边)都需要经过至少一次,要求总代价最小,可以用带下界的最小费用流解决。
从 1 以外的每个点向点 1 连边(对应 "重开游戏" 操作),正好可以把原图转化成一个无源汇图。
具体连边方法:
虚拟源汇 S 和 T。
对于每条边 u -> v:
从 S 向 v 连边,容量为 1,费用为 dis(u,v),限制至少走一次
从 u 向 v 连边,容量为 INF,费用为 dis(u,v),表示可以走多次
对于每个点 u
若 u!=1,从 u 向 1 连边,容量为 INF,费用为 0
从 u 向 T 连边,容量为 u 的出度,费用为 0
(思考一下可以发现这和有上下界的最大流的拆边方法相同)
然而跑出来特别慢,7s 才过,不知道 status 里那些几十 ms 的怎么做到的
- 1
- /*by SilverN*/
- 2#include 3#include 4#include 5#include 6#include 7#include 8 using namespace std;
- 9 const int INF = 0x3f3f3f3f;
- 10 const int mxn = 100010;
- 11 int read() {
- 12 int x = 0,
- f = 1;
- char ch = getchar();
- 13
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- 14
- while (ch >= '0' && ch <= '9') {
- x = x * 10 + ch - '0';
- ch = getchar();
- }
- 15
- return x * f;
- 16
- }
- 17 struct edge {
- 18 int u,
- v,
- nxt,
- f,
- w;
- 19
- }
- e[mxn];
- 20 int hd[650],
- mct = 1;
- 21 inline void add_edge(int u, int v, int f, int w) {
- 22 e[++mct].v = v;
- e[mct].u = u;
- e[mct].nxt = hd[u];
- e[mct].f = f;
- e[mct].w = w;
- hd[u] = mct;
- return;
- 23
- }
- 24 inline void insert(int u, int v, int f, int w) {
- 25 add_edge(u, v, f, w);
- add_edge(v, u, 0, -w);
- 26
- }
- 27 //
- 28 int n,
- m,
- K,
- S,
- T;
- 29 int dis[320],
- pre[320];
- 30 bool inq[320];
- 31 queue < int > q;
- 32 bool SPFA() {
- 33 memset(dis, 0x3f, sizeof dis);
- 34 q.push(S);
- dis[S] = 0;
- 35
- while (!q.empty()) {
- 36 int u = q.front();
- q.pop();
- inq[u] = 0;
- 37
- for (int i = hd[u]; i; i = e[i].nxt) {
- 38 int v = e[i].v;
- 39
- if (e[i].f && dis[v] > dis[u] + e[i].w) {
- 40 dis[v] = dis[u] + e[i].w;
- 41 pre[v] = i;
- 42
- if (!inq[v]) {
- inq[v] = 1;
- q.push(v);
- }
- 43
- }
- 44
- }
- 45
- }
- 46
- return dis[T] < INF;
- 47
- }
- 48 int MCF() {
- 49 int ans = 0;
- 50
- while (SPFA()) {
- 51 int tmp = INF;
- 52
- for (int i = pre[T]; i; i = pre[e[i].u]) tmp = min(tmp, e[i].f);
- 53 ans += tmp * dis[T];
- 54
- for (int i = pre[T]; i; i = pre[e[i].u]) e[i].f -= tmp,
- e[i ^ 1].f += tmp;
- 55
- }
- 56
- return ans;
- 57
- }
- 58 int main() {
- 59 // freopen("in.txt","r",stdin);
- 60 int i,
- j;
- 61 n = read();
- 62 S = 0;
- T = n + 1;
- 63 int a,
- u,
- v,
- w;
- 64
- for (i = 1; i <= n; i++) {
- 65 a = read();
- 66
- for (j = 1; j <= a; j++) {
- 67 v = read();
- w = read();
- 68 insert(S, v, 1, w);
- 69 insert(i, v, INF, w);
- 70
- }
- 71
- if (i != 1) {
- insert(i, 1, INF, 0);
- }
- 72 insert(i, T, a, 0);
- 73
- }
- 74 int ans = MCF();
- 75 printf("%d\n", ans);
- 76
- return 0;
- 77
- }
Bzoj3876 [Ahoi2014] 支线剧情
来源: http://www.bubuko.com/infodetail-2111948.html