题目描述
宅男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看完所有支线剧情所需要的最少时间。
题目解析
有1号剧情点,于是便有了源;有结束位置,于是便有了汇;每个剧情至少经过一次,于是便有了下界;每个剧情需要一定时间,于是便有了费用。合起来,它们就是有源汇有上下界最小费用流。
根据有上下界网络流的经典建模方法直接上即可。可参考有上下界网络流。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
/************************************************************** Problem: 3876 User: frank_c1 Language: C++ Result: Accepted Time:9920 ms Memory:3096 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to,cap,cost; }; const int maxn=305; const int siz=500000; const int INF=(int)(1e9); int fr[maxn]; edge e[maxn*maxn]; int d[maxn],p[maxn],a[maxn]; bool inq[maxn]; int n,m,s,t,fl,cs,tote=-1; inline void addone(int u,int v,int c,int s) { ++tote; e[tote].next=fr[u];fr[u]=tote; e[tote].to=v;e[tote].cap=c;e[tote].cost=s; } inline void addedge(int u,int v,int c,int s) { addone(u,v,c,s);addone(v,u,0,-s); } int q[maxn*maxn],l,r; bool SPFA() { REP(i,1,n+3) d[i]=INF; d[s]=p[s]=0;a[s]=INF;inq[s]=1; l=1;r=0;q[++r]=s; for(;l<=r;) { int x=q[l++]; inq[x]=0; RAL(i,x) if(e[i].cap>0 && d[e[i].to]>d[x]+e[i].cost) { d[e[i].to]=d[x]+e[i].cost; p[e[i].to]=i; a[e[i].to]=min(a[x],e[i].cap); if(!inq[e[i].to]) { if(d[e[i].to]<d[l]) q[--l]=e[i].to; else q[++r]=e[i].to; inq[e[i].to]=1; } } } if(d[t]==INF) return 0; fl+=a[t];cs+=a[t]*d[t]; int x=t; while(x!=s) { e[p[x]].cap-=a[t]; e[p[x]^1].cap+=a[t]; x=e[p[x]^1].to; } return 1; } void mincost() { fl=cs=0;while(SPFA()); } int main() { int a,w; read(n); s=n+2;t=n+3; memset(fr,-1,sizeof(fr)); REP(i,1,n) { if(i!=1) addedge(i,n+1,INF,0); read(m); REP(j,1,m) { read(a);read(w); addedge(i,a,INF,w); addedge(s,a,1,w); addedge(i,t,1,0); } } addedge(n+1,1,INF,0); mincost(); printf("%d\n",cs); return 0; } |