注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【分层图最大流】【星际转移问题】  

2014-01-28 15:55:26|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 显然在前面那些题目的基础上,我们可以YY出地球是源点,月球是汇点,然后太空站是中间节点,太空船则是边。 
 这一题的问题在于太空船是不断的移动的,也许我们移动到某一个太空站,再移动到另一个太空站所需要等待的时间是不同的,这是依据方案来定的,所以容量神马的就很难考虑了....这就是一个大问题...
  当然此是LRJ的黑书上的例题.所以就不再卖关子了...
   这个也是需要拆点的,我们假设需要时间T,那么我们把每个太空站和地球月球拆成T个点,表示T时刻时候它所在的状态,这样,假设这艘太空船T时刻在J,T+1时刻移动到K,那么我们就在T时刻的J和T+1时刻的K连一条有向边,容量为太空船的容量。然后还有一种情况就是等待,等待的话,对于其他太空站,我们在第T和第T+1个太空站连一条容量无穷的边即可,地球和月球由于到达了就可以流向汇了,所以不用连。
   咱们首先BFS出能否到达月球,不能的话直接输出无解(这点容易忽略),然后像魔术球一样从1开始枚举,每枚举一个时间增加边,跑最大流,然后判断最大流是否大于等于地球人数K,如果大于等于则停止,把当前时间输出即可。
  关于边,源点用-1表示,汇点用MAXN表示
  然后对于T时刻的各个节点用 T*(N+1)+i,i表示其标号,月球不是-1而是n+1即可。开始初始化时刻为0
  然后每枚举一个时间,先把当前地球和源连一条边,月球和汇连一条边,枚举每艘太空船当前位置和之前的位置,然后在这之间连边,容量为太空船容量。然后每一个新点和最后一个旧点连边。就可以了...
   这里再懒得写BFS了,直接判断到达一个特定的时间如果扩展流还是0的话就输出无解....
====================================================

program flow13; const maxn=1000; var g:array[-1..maxn,-1..maxn]of longint; d,que:array[-1..maxn]of longint; v:array[-1..maxn]of boolean; ship:array[1..20,0..40]of longint; num,r:array[1..20]of longint; n,m,max,tot:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function bfs(s,t,tot:longint):boolean; var l,r,i,u:longint; begin fillchar(que,sizeof(que),0); fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); l:=0;r:=1;que[l]:=s;v[s]:=true; while l<r do begin u:=que[l]; for i:=-1 to tot do if (g[u][i]>0)and(not v[i])then begin que[r]:=i; inc(r); d[i]:=d[u]+1; v[i]:=true; end; if (g[u][t]>0)and(not v[t]) then begin que[r]:=i; inc(r); d[t]:=d[u]+1; v[t]:=true; end; inc(l); end; exit(v[t]); end; function dfs(p,a,t,tot:longint):longint; var f,flow,i:longint; begin if (p=t)or(a=0) then exit(a); flow:=0; for i:=-1 to tot do if (g[p][i]>0)and(d[i]=d[p]+1)then begin f:=dfs(i,min(a,g[p][i]),t,tot); if f=0 then continue; inc(flow,f); inc(g[i][p],f); dec(g[p][i],f); dec(a,f); if a=0 then break; end; if (g[p][t]>0)and(d[t]=d[p]+1)then begin f:=dfs(t,min(a,g[p][t]),t,tot); inc(flow,f); inc(g[i][p],f); dec(g[p][i],f); dec(a,f); end; exit(flow); end; function dinic(s,t,tot:longint):longint; var ans:longint; begin ans:=0; while bfs(s,t,tot) do ans:=ans+dfs(s,maxlongint,t,tot); exit(ans); end; procedure init; var i,j,flow,t,add,w,u,v,maxt,ans:longint; begin read(n,m,max); fillchar(g,sizeof(g),255); maxt:=0; for i:=1 to m do begin read(r[i]); read(num[i]); if maxt<num[i] then maxt:=num[i]; for j:=0 to num[i]-1 do read(ship[i][j]); end; inc(n,2); g[-1][0]:=maxlongint; g[0][-1]:=0; g[n-1][maxn]:=maxlongint; g[maxn][n-1]:=0; t:=0;tot:=0; while true do begin inc(t); add:=t*n; g[-1][add]:=maxlongint; g[add][-1]:=0; g[n-1+add][maxn]:=maxlongint; g[maxn][n-1+add]:=0; for i:=1 to n-2 do begin g[i+add-n][i+add]:=maxlongint; g[i+add][i+add-n]:=0; end; for i:=1 to m do begin w:=t mod num[i]; u:=ship[i][(w+num[i]-1)mod num[i]]; v:=ship[i][w]; if u=-1 then u:=n-1; if v=-1 then v:=n-1; g[u+add-n][v+add]:=r[i]; g[v+add][u+add-n]:=0; end; ans:=dinic(-1,maxn,add+n-1); tot:=tot+ans; if tot>=max then break; if (t>maxt shl 1)and(tot=0) then begin writeln(0);exit;end; end; writeln(t); end; begin assign(input,'f.in');reset(input); init; close(input); end.
  评论这张
 
阅读(24)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018