本文共 1670 字，大约阅读时间需要 5 分钟。

题目大意： 有 $n$ 个空间站，有 $k$ 个人需要从地球到月球，有 $m$ 个飞船在空间站、地球、月球之间周期性地行驶，从一个地方飞到另一个地方的时间为 $1$ 天，问将 $k$ 个人都送到的最短时间是多少。

题解

由于这题 $n$ 很小，所以可以建分层图，每一层代表一天。两层间对应的点之间连边，流量为 $\infty$，表示空间站中的人可以等一天不上别的飞船。然后飞船在第 $i$ 天到 $i+1$ 天时从 $a$ 飞到 $b$ 时，从第 $i$ 层的点 $a$ 向第 $i+1$ 层的点 $b$ 连一条流量为飞船最大载客量的边。

以及，超级源点向每层的地球连边，流量无限，每层的月球也向超级汇点连边。

然后一天建一层，哪天能够把 $k$ 个人都送出去时，就停止输出答案即可。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 30#define maxm 10010#define inf 999999999int n,m,k,S,T;int h[maxn],r[maxn],s[maxn][maxn],now[maxn];struct edge{
   int y,z,next;};edge e[maxm];int first[maxm],len=1;void buildroad(int x,int y,int z){
   	e[++len]=(edge){
   y,z,first[x]};	first[x]=len;}int fa[maxn];int findfa(int x){
   return x==fa[x]?x:fa[x]=findfa(fa[x]);}void link(int x,int y){
   	x=findfa(x);y=findfa(y);	if(x!=y)fa[y]=x;}int deep[maxm],q[maxm],st,ed;bool bfs(){
   	memset(deep,0,sizeof(deep));	st=ed=1;q[st]=S;deep[S]=1;	while(st<=ed)	{
   		int x=q[st++];		for(int i=first[x];i;i=e[i].next)		if(!deep[e[i].y]&&e[i].z)deep[q[++ed]=e[i].y]=deep[x]+1;	}	return deep[T];}int dfs(int x,int flow){
   	if(x==T)return flow;	int tt=0;	for(int i=first[x];i;i=e[i].next)	{
   		int y=e[i].y;		if(deep[y]==deep[x]+1&&e[i].z)		{
   			int p=dfs(y,min(e[i].z,flow-tt));tt+=p;			e[i].z-=p;e[i^1].z+=p;			if(tt==flow)break;		}	}	if(!tt)deep[x]=0;	return tt;}int main(){
   	scanf("%d %d %d",&n,&m,&k);n+=4;	for(int i=1;i<=n;i++)fa[i]=i;	for(int i=1;i<=m;i++)	{
   		scanf("%d %d",&h[i],&r[i]);		for(int j=1;j<=r[i];j++)		{
   			scanf("%d",&s[i][j]);			if(s[i][j]==0)s[i][j]=n-3;			if(s[i][j]==-1)s[i][j]=n-2;		}		for(int j=1;j
     
    
   

转载地址：http://hcnib.baihongyu.com/