首页 > 代码库 > [CTSC1999]【网络流24题】星际转移

[CTSC1999]【网络流24题】星际转移

2024-09-05 16:49:47   220人阅读

Description

由于人类对自然资源的消耗，人们意识到大约在2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空站 位于地球与月球之间，且有m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船i 只可容纳H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站134134134…。每一艘太 空船从一个太空站驶往任一太空站耗时均为1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上，太空船全在初始站。
试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

Input

第1行有3 个正整数n（太空站个数），m（太空船个数）和k（需要运送的地球上的人的个数）。其中 1<=m<=13, 1<=n<=20, 1<=k<=50。
接下来的m行给出太空船的信息。第i+1 行说明太空船pi。第1 个数表示pi 可容纳的人数Hpi；第2 个数表示pi 一个周期停靠的太空站个数r，1<=r<=n+2；随后r 个数是停靠的太空站的编号(Si1,Si2,…,Sir)，地球用0 表示，月球用-1 表示。时刻0 时，所有太空船都在初始站，然后开始运行。在时刻1，2，3…等正点时刻各艘太空船停靠相应的太空站。人只有在0,1,2…等正点时刻才能上下太空船。

Output

将全部人员安全转移所需的时间，如果问题无解，则输出0。

Sample Input

2 2 1
1 3 0 1 2
1 3 1 2 -1

Sample Output

5

正解：网络判定+最大流。

可以二分答案，不过不如枚举时间，直接动态加边，然后在残量网络中增广。从源点向第0天的地球连容量为k的边，从第i天的星球向第i+1的星球连容量为inf的边，如果第i天到第i+1天有飞船经过，则连一条飞船容量的边。这样我们就能解决这个问题了。

 

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define inf (1<<30)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define c(t,i) ( t*(n+2)+i )
19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
20 
21 using namespace std;
22 
23 struct edge{ int nt,to,flow,cap; }g[1000010];
24 
25 int head[100010],d[100010],q[100010],p[100010],r[100010],s[1010][1010],n,m,k,S,T,flow,num=1;
26 
27 il int gi(){
28     RG int x=0,q=1; RG char ch=getchar(); while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();
29     if (ch==‘-‘) q=-1,ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); return q*x;
30 }
31 
32 il void insert(RG int from,RG int to,RG int cap){ g[++num]=(edge){head[from],to,0,cap},head[from]=num; return; }
33 
34 il int bfs(RG int S,RG int T){
35     memset(d,0,sizeof(d)); RG int h=0,t=1; q[t]=S,d[S]=1;
36     while (h<t){
37     RG int x=q[++h];
38     for (RG int i=head[x];i;i=g[i].nt){
39         RG int v=g[i].to;
40         if (!d[v] && g[i].cap>g[i].flow){
41         q[++t]=v,d[v]=d[x]+1;
42         if (v==T) return 1;
43         }
44     }
45     }
46     return 0;
47 }
48 
49 il int dfs(RG int x,RG int T,RG int a){
50     if (x==T || !a) return a; RG int f,flow=0;
51     for (RG int i=head[x];i;i=g[i].nt){
52     RG int v=g[i].to;
53     if (d[v]==d[x]+1 && g[i].cap>g[i].flow){
54         f=dfs(v,T,min(a,g[i].cap-g[i].flow));
55         g[i].flow+=f,g[i^1].flow-=f;
56         flow+=f,a-=f; if (!a) return flow;
57     }
58     }
59     if (!flow) d[x]=-1; return flow;
60 }
61 
62 il int maxflow(RG int S,RG int T){ while (bfs(S,T)) flow+=dfs(S,T,inf); return flow; }
63 
64 il void work(){
65     n=gi(),m=gi(),k=gi(); S=100001,T=100002;
66     for (RG int i=1;i<=m;++i){
67     p[i]=gi(),r[i]=gi();
68     for (RG int j=1;j<=r[i];++j){
69         s[i][j]=gi(); if (s[i][j]==0) s[i][j]=n+1;
70         if (s[i][j]==-1) s[i][j]=n+2;
71     }
72     }
73     insert(S,n+1,k),insert(n+1,S,0);
74     for (RG int ans=1;ans<=(k+2)*(n+2);++ans){
75     for (RG int i=1;i<=n+2;++i) insert(c((ans-1),i),c(ans,i),inf),insert(c(ans,i),c((ans-1),i),0);
76     for (RG int i=1;i<=m;++i){
77         insert(c((ans-1),s[i][(ans-1)%r[i]+1]),c(ans,s[i][ans%r[i]+1]),p[i]);
78         insert(c(ans,s[i][ans%r[i]+1]),c((ans-1),s[i][(ans-1)%r[i]+1]),0);
79     }
80     insert(c(ans,(n+2)),T,inf),insert(T,c(ans,(n+2)),0);
81     if (maxflow(S,T)==k){ printf("%d\n",ans); return; }
82     }
83     printf("0"); return;
84 }
85 
86 int main(){
87     File("star");
88     work();
89     return 0;
90 }

 

[CTSC1999]【网络流24题】星际转移


联系
我们