题意：
• 由于人类对自然资源的消耗，人们意识到大约在2300 年之后，地球就不能再居住了。于是在
月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空站位于地球与月球之间，且有m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船i 只可容纳H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的
运输方案。
• 编程任务：对于给定的太空船的信息，找到让所有人尽快地全部转移到月球上的运输方案。
• 1<=m<=13, 1<=n<=20, 1<=k<=50
题解：
分层图+网络流
分层图不难看出，但是本题不同于一般的分层图，本题是动态的，一般的分层图在跑图之前就已经建好，但是本题是跑一次建一次，为什么？因为在本题中公共交通天空船是移动的，就比如太空船A可以从1到2，太空船B可以从2到3，那么从1到3是不是就花费2？并不是因为我们从1到2的时候，船B不一定正好也在2的位置，也就相当于我们平时坐车时，你到公交站并不是直接上车，要等待车到，所以分层图是按照时间（天数）来分成，没多一天就新添几条路，添加的就是该填所有车能走的路
当网络流跑出的结果大于等于所有人数时，说明就逃脱成功了，且当前答案就是最小花费
建图的具体方法：
层: 0到t层，表示时间，每层有(n+2)个点数.
源点: 0
汇点: (n+2) * t+n+1（第t层的月球）
第f层地球: (n+2) * f+0
第f层空间站i: (n+2) * f+i
第f层月球: (n+2) * f+n+1
弧:
(t层节点, t+1层对应节点, INF)
(t层节点, t时刻飞船路径到达的节点, 飞船容量)
最大流:
满足最大流大于等于初始人数的最小时间t即为答案
有个博主写的算法框架很好
代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f,M=1000005;
int n,m,k,s,t,tot=1,ans,mx;
int f[100],p[100],g[100][100],num[100];//这里不开这么大第二个点会RE，不知道为什么
int ne[M],to[M],h[M],flow[M],lev[M],q[M];
int find(int x) {
if(f[x]==x) return x;
f[x]=find(f[x]);return f[x];
}
void uni(int x,int y) {//并查集的连接操作
x=find(x),y=find(y);
if(x!=y) f[x]=y;
}
void add(int x,int y,int z) {
to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z;
to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0;
}
int dfs(int x,int liu) {
if(x==t) return liu;
int kl,sum=0;
for(int i=h[x];i;i=ne[i])
if(flow[i]>0&&lev[to[i]]==lev[x]+1) {
kl=dfs(to[i],min(flow[i],liu-sum));
sum+=kl,flow[i]-=kl,flow[i^1]+=kl;
if(sum==liu) return sum;
}
return sum;
}
int bfs() {
for(int i=1;i<=ans*(n+1);++i) lev[i]=0;
int he=1,ta=1,x;lev[t]=0,q[1]=s;
while(he<=ta) {
x=q[he],++he;
if(x==t) return 1;
for(int i=h[x];i;i=ne[i])
if(flow[i]>0&&!lev[to[i]])
lev[to[i]]=lev[x]+1,q[++ta]=to[i];
}
return 0;
}
int main()
{
int x,y;
scanf("%d%d%d",&n,&m,&k);
s=0,t=M;
for(int i=1;i<=n+2;++i) f[i]=i;
for(int i=1;i<=m;++i) {
scanf("%d%d",&p[i],&num[i]);
for(int j=0;j<num[i];++j) {
scanf("%d",&g[i][j]);
if(g[i][j]==0) g[i][j]=n+1;//地球
if(g[i][j]==-1) g[i][j]=n+2;//月亮
if(j!=0) uni(g[i][j-1],g[i][j]);
}
}
if(find(n+1)!=find(n+2)) {puts("0");return 0;}//如果没有转移方案
for(ans=1;;++ans) {//枚举答案
add(s,(ans-1)*(n+1)+n+1,inf);//n+1是地球，汇点是月球。向地球连inf的边
for(int i=1;i<=m;++i) {
x=(ans-1)%num[i],y=ans%num[i];
if(g[i][x]==n+2) x=t;
else x=(ans-1)*(n+1)+g[i][x];
if(g[i][y]==n+2) y=t;
else y=ans*(n+1)+g[i][y];
add(x,y,p[i]);//一艘飞船一条边
}
while(bfs()) mx+=dfs(s,inf);//dinic网络流
if(mx>=k) {printf("%d\n",ans);return 0;}
for(int i=1;i<=n+1;++i) add((ans-1)*(n+1)+i,ans*(n+1)+i,inf);//时间间的转移
}
return 0;
}
京公网安备 11010502036488号