【网络流24题】CTSC 1999 家园 / 星际转移问题 题解

题解"/>

【网络流24题】CTSC 1999 家园 / 星际转移问题 题解

题目传送门

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

题解

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

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

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

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
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<r[i];j++)link(s[i][j],s[i][j+1]);now[i]=1;}if(findfa(n-3)!=findfa(n-2))return printf("0"),0;int day=0,tot=0;S=n-1,T=S+1;buildroad(S,n-3,inf),buildroad(n-3,S,0);buildroad(n-2,T,inf),buildroad(T,n-2,0);while(tot<k){day++;for(int i=1;i<=n-2;i++)//两层之间相应的点连边，流量无限buildroad(i+(day-1)*n,i+day*n,inf),buildroad(i+day*n,i+(day-1)*n,0);for(int i=1;i<=m;i++)//第day-1天向第day天的点连边buildroad(s[i][now[i]]+(day-1)*n,s[i][now[i]%r[i]+1]+day*n,h[i]),buildroad(s[i][now[i]%r[i]+1]+day*n,s[i][now[i]]+(day-1)*n,0),now[i]=now[i]%r[i]+1;buildroad(S,n-3+day*n,inf),buildroad(n-3+day*n,S,0);//源点向地球连边buildroad(n-2+day*n,T,inf),buildroad(T,n-2+day*n,0);//月球向汇点连边while(bfs())tot+=dfs(S,inf);}printf("%d",day);
}