题目背景
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。
解题思路：
假如说告诉你多少天，问转移人口，那是不是会好一些，
按时间分层，不同层相同点间按照时间方向建$inf$的边，
跑一边最大流，源点是0时刻的地球，汇点是T时刻的月球。
最大流就是人口。
所以枚举判断好了。
代码：
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int oo=0x3f3f3f3f;
struct pnt{
int hd;
int lyr;
int now;
}p[];
struct ent{
int twd;
int lst;
int vls;
}e[];
int cnt;
int n,m,k;
int s,t;
int size;
int H[];
int fa[];
std::queue<int>Q;
std::vector<int>st[];
void ade(int f,int t,int v)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
bool Bfs(void)
{
while(!Q.empty())
Q.pop();
for(int i=;i<=size;i++)
p[i].lyr=;
p[s].lyr=;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==&&e[i].vls>)
{
p[to].lyr=p[x].lyr+;
if(to==t)
return true;
Q.push(to);
}
}
}
return false;
}
int Dfs(int x,int fll)
{
if(x==t)
return fll;
for(int& i=p[x].now;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==p[x].lyr+&&e[i].vls>)
{
int ans=Dfs(to,std::min(fll,e[i].vls));
if(ans>)
{
e[i].vls-=ans;
e[((i-)^)+].vls+=ans;
return ans;
}
}
}
return ;
}
int Dinic(void)
{
int ans=;
while(Bfs())
{
for(int i=;i<=size;i++)
p[i].now=p[i].hd;
int dlt;
while(dlt=Dfs(s,oo))
ans+=dlt;
}
return ans;
}
int finf(int x)
{
return fa[x]==x?x:fa[x]=finf(fa[x]);
}
int main()
{
// freopen("a.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n+m+;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
scanf("%d",&H[i]);
int tmp;
scanf("%d",&tmp);
for(int j=;j<=tmp;j++)
{
int tl;
scanf("%d",&tl);
if(tl==)tl=n+;
if(tl==-)tl=n+;
st[i].push_back(tl);
int f1=finf(tl);
int f2=finf(n++i);
if(f1!=f2)
fa[f1]=f2;
}
}
if(finf(n+)!=finf(n+))
{
printf("%d\n",);
return ;
}
s=n+;
int N;
int popu=;
for(N=;;N++)
{
if(N)
{
for(int i=;i<=n+m+;i++)
{
ade((N-)*(n+m+)+i,N*(n+m+)+i,oo);
ade(N*(n+m+)+i,(N-)*(n+m+)+i,);
}
}
size=(N+)*(n+m+);
t=N*(n+m+)+n+;
for(int i=;i<=m;i++)
{
int tp=st[i][N%st[i].size()];
if(tp!=n+)
{
ade(N*(n+m+)+n++i,N*(n+m+)+tp,H[i]);
ade(N*(n+m+)+tp,N*(n+m+)+n++i,);
}
if(tp!=n+)
{
ade(N*(n+m+)+tp,N*(n+m+)+n++i,H[i]);
ade(N*(n+m+)+n++i,N*(n+m+)+tp,);
}
}
popu+=Dinic();
if(popu<k);else break;
}
printf("%d\n",N);
return ;
}