###Description
###【故事背景】宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。###【问题描述】JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0，则说明i号剧情点是游戏的一个结局了。JYY观看一个支线剧情需要一定的时间。JYY一开始处在1号剧情点，也就是游戏的开始。显然任何一个剧情点都是从1号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于JYY过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，所以JYY要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到1号剧情点。JYY可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦，JYY希望花费最少的时间，看完所有不同的支线剧情。
###Input
输入一行包含一个正整数N。接下来N行，第i行为i号剧情点的信息；第一个整数为，接下来个整数对，Bij和Tij，表示从剧情点i可以前往剧情点，并且观看这段支线剧情需要花费的时间。
###Output
输出一行包含一个整数，表示JYY看完所有支线剧情所需要的最少时间。
###Sample Input
62 2 1 3 22 4 3 5 42 5 5 6 6000###Sample Output
24
###HINT
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
有上下界的网络流
/************************************************************** ???Problem: 3876 ???User: s_a_b_e_r ???Language: C++ ???Result: Accepted ???Time:272 ms ???Memory:1820 kb****************************************************************/ #include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<queue>#include<vector> #define ll long long #include<cstring>using namespace std;inline int read(){ ???int an=0,f=1; ???char ch=getchar(); ???while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} ???while(ch<=‘9‘&&ch>=‘0‘){an=an*10+(ch^48);ch=getchar();} ???return an*f;}const int maxn=1000,maxm=maxn*30;const int INT=1e7;int in[maxn],S,T,X,Y,out[maxn],f[maxn],cnt=1;int n;struct saber{int nex,to,lim,wi;};ll ans;vector<saber>b;inline void add(int x,int y,int z,int wi){ ???cnt++; ???b.push_back( ?(saber){f[x],y,z,wi} ); ???f[x]=cnt;}inline void prepare(){ ???n=read();S=n+2;T=n+1; ???b.push_back( (saber){0,0,0,0} ); ???b.push_back( (saber){0,0,0,0} ); ???for(int i=2;i<=n;i++){add(i,1,INT,0),add(1,i,0,0);} ???for(int i=1;i<=n;i++){ ???????out[i]=read(); ???????for(int j=1;j<=out[i];j++){ ???????int x=read(),y=read(); ???????add(i,x,INT,y); ???????add(x,i,0,-y); ???????in[x]++; ???????ans+=y; ???????} ???} ??????for(int i=1;i<=n;i++){ ???????int x=in[i]-out[i]; ???????if(x<0){ ???????????add(i,T,-x,0); ???????????add(T,i,0,0); ???????} ???????else{ ???????????add(S,i,x,0); ???????????add(i,S,0,0); ???????} ???}}queue<int>q;int dis[maxn];bool vis[maxn];bool ind[maxn];inline int bfs(){ ???while(!q.empty())q.pop(); ???q.push(S); ???for(int i=1;i<=S+9;i++)dis[i]=INT; ???dis[S]=0; ???while(!q.empty()){ ???????int x=q.front();q.pop(); ???????vis[x]=0; ???????for(int i=f[x];i;i=b[i].nex){ ???????????int v=b[i].to; ???????????if(dis[v]>dis[x]+b[i].wi&&b[i].lim){ ???????????????dis[v]=dis[x]+b[i].wi; ???????????????if(!vis[v]){vis[v]=1;q.push(v);} ???????????} ???????} ???} ???return dis[T]!=INT;} ?inline int dfs(int x,int li){ ???int used=li;ind[x]=1; ???if(x==T||!li)return li; ???for(int i=f[x];i&&used;i=b[i].nex){ ???????int v=b[i].to; ???????if(ind[v])continue; ???????if(dis[v]==dis[x]+b[i].wi&&b[i].lim){ ???????????int re=dfs( v,min(used,b[i].lim) ); ???????????b[i].lim-=re; ???????????b[i^1].lim+=re; ???????????used-=re; ???????} ???} ???return li-used;}inline void dinic(){ ???while(bfs()){ ???????memset(ind,0,sizeof ind); ???????ans+=dis[T]*dfs(S,INT); ???} ???cout<<ans;}int main(){ ???ios::sync_with_stdio(0); ???prepare(); ???dinic(); ???return 0;}QAQ网络流又写挂了，害得我查了好久>_<
有上下界的最小费用流~熟悉的套路x
- 对于每个有连边的点对(u,v)，从u向v连一条费用为w，流量为inf的边，表示这段剧情最多能看无数遍；再从源点向v连一条费用w流量1的点，表示至少看一次
- 对于每个除1以外的点，向1连一条流量inf费用0的边，代表随时可以回到点1
- 对于每个点，向汇点连流量为该点出度，费用为0的边，因为每条边至少走一遍，对于这个点至少预留out的流量
于是跑最小费用最大流就好啦>_<
/************************************************************** ???Problem: 3876 ???User: wypx ???Language: C++ ???Result: Accepted ???Time:9380 ms ???Memory:40364 kb****************************************************************/ #include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int N=500,M=10*N*N,inf=1e9+7;int n,out[N],S,T,cnt=1,p[N],inp[N];int dis[N],in[N];bool vis[N];struct edge{int to,nex,val,cos;}e[M];void add(int u,int v,int lim,int cos){ ???e[++cnt]=(edge){v,p[u],lim,cos}; ???p[u]=cnt; ???e[++cnt]=(edge){u,p[v],0,-cos}; ???p[v]=cnt;}queue<int>q;bool spfa(){ ???for(int i=1;i<=T;++i)dis[i]=inf; ???memset(in,0,sizeof(in)); ???while(!q.empty())q.pop(); ???dis[S]=0;q.push(S); ???while(!q.empty()){ ???????int x=q.front();q.pop();in[x]=0; ???????for(int i=p[x];i;i=e[i].nex){ ???????????int v=e[i].to; ???????????if(e[i].val&&dis[v]>dis[x]+e[i].cos){ ???????????????dis[v]=dis[x]+e[i].cos; ???????????????if(!in[v]){in[v]=1;q.push(v);} ???????????} ???????} ???} ???return dis[T]<inf;} int dfs(int x,int li){ ???vis[x]=1; ???if(x==T)return li; ???int used=li; ???for(int i=p[x];i;i=e[i].nex){ ???????int v=e[i].to; ???????if(!vis[v]&&used&&e[i].val&&dis[v]==dis[x]+e[i].cos){ ???????????int re=dfs(v,min(used,e[i].val)); ???????????used-=re; ???????????e[i].val-=re; ???????????e[i^1].val+=re; ???????} ???} ???return li-used;}int dinic(){ ???int ans=0; ???while(spfa()){ ???????memset(vis,0,sizeof(vis)); ???????ans+=dfs(S,inf)*dis[T]; ???} ???return ans;}int main(){ ???scanf("%d",&n);S=n+1,T=n+2; ???for(int i=1;i<=n;++i){ ???????scanf("%d",&out[i]); ???????for(int j=1;j<=out[i];++j){ ???????????int v,w;scanf("%d%d",&v,&w); ???????????add(i,v,inf,w); ???????????add(S,v,1,w); ???????} ???????add(i,T,out[i],0); ???????if(i!=1)add(i,1,inf,0); ???} ???cout<<dinic()<<endl; ???return 0;}