【BZOJ3876】[Ahoi2014]支線劇情

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

6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

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

題解：初學了有上下界費用流，趕緊水一發~

有上下界費用流其實跟有上下界最大流都差不多，都是新建原、匯，然后將下界全都放到新建的原匯上搞定，剩余的用原圖搞定，具體方法：對于邊(i,j)，設它的長度為len

1.S -> j 容量1，費用len 相當于(i,j)的下界
2.i -> T 容量1，費用0 也相當于(i,j)的下界
3.i -> j 容量∞，費用len 相當于(i,j)上界無窮大
4.i -> S 容量∞，費用0 相當于每個點都向原圖的匯點連一條邊，但是由于匯點到源點還要連一條費用0的邊，所以就將原圖匯點省略了（也可以理解為在任意一個位置都可以結束，所以任意一個點都是匯點）

然后正常的跑費用流就行了

#include <cstdio> #include <iostream> #include <queue> #include <cstring> using namespace std; int n,m,cnt,S,T,ans; int dis[500],inq[500],to[300000],next[300000],cost[300000],flow[300000],pe[500],pv[500],head[500]; queue<int> q; void add(int a,int b,int c,int d) {to[cnt]=b,cost[cnt]=c,flow[cnt]=d,next[cnt]=head[a],head[a]=cnt++;to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++; } int bfs() {int i,u;memset(dis,0x3f,sizeof(dis));dis[S]=0,q.push(S);while(!q.empty()){u=q.front(),q.pop(),inq[u]=0;for(i=head[u];i!=-1;i=next[i]){if(dis[to[i]]>dis[u]+cost[i]&&flow[i]){dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);}}}return dis[T]<0x3f3f3f3f; } int rd() {int ret=0; char gc=getchar();while(gc<'0'||gc>'9') gc=getchar();while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret; } int main() {memset(head,-1,sizeof(head));int i,j,k,a,b,c;n=rd();S=0,T=n+1;for(i=1;i<=n;i++){a=rd();for(j=1;j<=a;j++){b=rd(),c=rd();add(i,b,c,1<<30),add(S,b,c,1);}if(a) add(i,T,0,a);if(i!=1) add(i,1,0,1<<30);}while(bfs()){int mf=1<<30;for(i=T;i;i=pv[i]) mf=min(mf,flow[pe[i]]);ans+=dis[T]*mf;for(i=T;i;i=pv[i]) flow[pe[i]]-=mf,flow[pe[i]^1]+=mf;}printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/CQzhangyu/p/6831638.html

總結

以上是生活随笔為你收集整理的【BZOJ3876】[Ahoi2014]支线剧情 有上下界费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

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