时空限制1000ms / 128MB
题目背景
none!
题目描述
由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有 n 个太空站位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站 134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。
初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。
对于给定的太空船的信息，找到让所有人尽快地全部转移到月球上的运输方案。
输入输出格式
输入格式：第 1 行有 3 个正整数 n（太空站个数），m（太空船个数）和 k（需要运送的地球上的人的个数）。其中 n<=13 m<=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…等正点时刻才能上下太空船。
输出格式：程序运行结束时，将全部人员安全转移所需的时间输出。如果问题
无解，则输出 0。
输入输出样例
2 2 11 3 0 1 21 3 1 2 -1
5
说明
题目链接：
分层图+最大流。这个题目的难点在于不同时间时，图中的边也是不同的，因此我们可以对每一时间都建一层图，层之间按照题目的约束建边，即若某一时间太空船在点u，下一时刻到点v，我们就在当前时刻对应的层的u点和下一时刻对应的层的v点之间连一条容量为太空船容量的边，又因为太空站可以容纳无限多的人，所以对于当前层的点，还要与下一层对应的点连一条容量为INF的边。最后超级源点与每一层的地球连边，每一层的月球与超级汇点连边。这样建图，每增加一层图，就代表时间加一。我们先把无解的情况用并查集判出，然后边建图边跑最大流，直到最大流量大于给定的人数为止。
#include#define INF LLONG_MAX/2#define N 10005using namespace std;typedef struct{ int to,next; long long flow;}ss;ss edg[N*4];int now_edge=0,s,t;int head[N];void addedge(int u,int v,long long flow){ edg[now_edge]=(ss){v,head[u],flow}; head[u]=now_edge++; edg[now_edge]=(ss){u,head[v],0}; head[v]=now_edge++;}int dis[N];bool bfs(){ memset(dis,0,sizeof(dis)); queue q; q.push(s); dis[s]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edg[i].next) { ss &e=edg[i]; if(e.flow>0&&dis[e.to]==0) { dis[e.to]=dis[now]+1; q.push(e.to); } } } if(dis[t]==0)return 0; return 1;}int current[N];long long dfs(int x,long long maxflow){ if(x==t)return maxflow;// printf("%d %lld\n",x,maxflow); for(int i=current[x];i!=-1;i=edg[i].next) { current[x]=i; ss &e=edg[i]; if(e.flow>0&&dis[e.to]==dis[x]+1) { long long flow=dfs(e.to,min(maxflow,e.flow)); if(flow!=0) { e.flow-=flow; edg[i^1].flow+=flow; return flow; } } } return 0;}long long dinic(){ long long ans=0,flow; while(bfs()) { for(int i=0;i