题目描述
【故事背景】
宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往
都有很多的支线剧情,现在JYY想花费最少的时间看完所有的支线剧情。
【问题描述】
JYY现在所玩的RPG游戏中,一共有N个剧情点,由1到N编号,第i个剧情点可以根据JYY的不同的选择,而经过不同的支线剧情,前往Ki种不同的新的剧情点。当然如果为0,则说明i号剧情点是游戏的一个结局了。
JYY观看一个支线剧情需要一定的时间。JYY一开始处在1号剧情点,也就是游戏的开始。显然任何一个剧情点都是从1号剧情点可达的。此外,随着游戏的进行,剧情是不可逆的。所以游戏保证从任意剧情点出发,都不能再回到这个剧情点。由于JYY过度使用修改器,导致游戏的“存档”和“读档”功能损坏了,
所以JYY要想回到之前的剧情点,唯一的方法就是退出当前游戏,并开始新的游戏,也就是回到1号剧情点。JYY可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦,JYY希望花费最少的时间,看完所有不同的支线剧情。
输入
输入一行包含一个正整数N。
接下来N行,第i行为i号剧情点的信息;
第一个整数为,接下来个整数对,Bij和Tij,表示从剧情点i可以前往剧
情点,并且观看这段支线剧情需要花费的时间。
输出
输出一行包含一个整数,表示JYY看完所有支线剧情所需要的最少时间。
样例输入
6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0
样例输出
24
提示
JYY需要重新开始3次游戏,加上一开始的一次游戏,4次游戏的进程是
1->2->4,1->2->5,1->3->5和1->3->6。
对于100%的数据满足N<=300,0<=Ki<=50,1<=Tij<=300,Sigma(Ki)<=5000
可以发现题中给出的图是一个拓扑图,我们只需要按题意连边然后跑有上下界的费用流即可,每条边的流量下限为$1$。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<bitset> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int S,T,SS,TT; int n,ans; int tot=1; int head[510]; int to[30010]; int nex[30010]; int v[30010]; int c[30010]; int from[30010]; int f[510]; int d[510]; int vis[510]; int x,y,k; queue<int>q; void add(int x,int y,int z,int w) { nex[++tot]=head[x]; head[x]=tot; to[tot]=y; v[tot]=z; c[tot]=w; from[tot]=x; nex[++tot]=head[y]; head[y]=tot; to[tot]=x; v[tot]=-z; c[tot]=0; from[tot]=y; } void result(int S,int T) { int now=T; int flow=1<<30; while(now!=S) { flow=min(flow,c[f[now]]); now=from[f[now]]; } ans+=d[T]*flow; now=T; while(now!=S) { c[f[now]]-=flow; c[f[now]^1]+=flow; now=from[f[now]]; } } bool SPFA(int S,int T) { while(!q.empty()) { q.pop(); } for(int i=1;i<=n+4;i++) { d[i]=1<<30; } d[S]=0; vis[S]=1; q.push(S); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i;i=nex[i]) { if(!c[i]) { continue; } if(d[to[i]]>d[now]+v[i]) { d[to[i]]=d[now]+v[i]; f[to[i]]=i; if(!vis[to[i]]) { q.push(to[i]); vis[to[i]]=1; } } } } return d[T]!=(1<<30); } void min_cost(int S,int T) { while(SPFA(S,T)) { result(S,T); } } int main() { scanf("%d",&n); S=n+1,T=n+2,SS=n+3,TT=n+4; for(int i=1;i<=n;i++) { scanf("%d",&k); if(k) { add(i,T,0,k); } while(k--) { scanf("%d%d",&x,&y); add(S,x,y,1); add(i,x,y,1<<30); } } add(SS,1,0,1<<30); for(int i=2;i<=n;i++) { add(i,TT,0,1<<30); } add(TT,SS,0,1<<30); min_cost(S,T); printf("%d ",ans); }