「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
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
题解
大爷题解传送门 http://blog.csdn.net/popoqqq/article/details/43024221
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-8 #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; int ans,n,K,cnt=1; int last[305],q[305],dis[305]; bool mark[305]; struct edge{ int to,next,v,c; }e[100005]; void insert(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { int head=0,tail=1; q[0]=T;dis[T]=0;mark[T]=1; for(int i=0;i<T;i++)dis[i]=inf; memset(mark,0,sizeof(mark)); while(head!=tail) { int now=q[head];//cout<<now<<' '; head++;if(head==305)head=0; mark[now]=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].v&&dis[now]-e[i].c<dis[e[i].to]) { dis[e[i].to]=dis[now]-e[i].c; if(!mark[e[i].to]) mark[e[i].to]=1,q[tail++]=e[i].to; if(tail==305)tail=0; } } return dis[0]!=inf; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(dis[x]-e[i].c==dis[e[i].to]&&!mark[e[i].to]&&e[i].v) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; ans+=e[i].c*w; used+=w;if(used==f)return f; } return used; } int zkw() { int tmp=0; while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); tmp+=dfs(0,inf); } } return tmp; } int main() { n=read();T=n+1; int b,t; for(int i=1;i<=n;i++) { K=read(); insert(i,T,K,0); insert(i,1,inf,0); for(int j=1;j<=K;j++) { b=read();t=read(); insert(i,b,inf,t); insert(0,b,1,t); } } zkw(); printf("%d",ans); return 0; } |
就算上下界也写的有问题= =跑得太慢了。。S到每个点不用一条边一条边加= =
Orz!
Orz
为啥你们都写上下界费用流啊
先floyed,直接把所有点按出度和入度的大小关系分类,建一个类似二分图的模型就行了啊
噢原来如此我是当做模板练习TAT
原来如此- – 看来我傻叉了- –
这种写法不是上下界吧。。
其实是的,只不过没有记那个数组,直接连了
上下界不是用-inf的那种么