原题链接：http://codevs.cn/problem/1034/
由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有n个太空站处于地球与月球之间（编号1..n），m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi，将周期性地停靠一系列的太空站（Si1,Si2…Sir），如：（1，3，4）表示停靠太空站1 3 4 1 3 4 1 3 4 …。 任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船pi处于Si1），目标是让所有的人尽快地全部转移到月球上。
文件第一行为三个正整数 n（太空站个数）、 m（太空船个数）、 k（需要运送的地球上的人的个数），其中 1<=m<=13, 1<=n<=20, 1<=k<=50。
接下来的n行给出了太空船的信息，第i+1行说明太空船pi，此行第一个数表示pi可容纳的人数Hpi，第二个数表示pi停靠一个周期的太空站个数r，1<=r<=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir), 地球用0表示，月球用-1表示。0时刻时，所有太空船都在初始站，随后开始运行，在时刻1，2，3…等正点时刻各艘太空船停靠相应的太空站，即人只有在0,1,2…等正点时刻才能上下太空船。
文件只有一个数，若问题有解，输出完成全部人员安全转移的时刻，否则输出0。
2 2 1
1 3 0 1 2
1 3 1 2 –1
5
1<=m<=13, 1<=n<=20, 1<=k<=50。
枚举时间t，每增加一单位时间，就增加一列点，这一列的点的序号是(0,t),(1,t)...(n,t)，其中第一个数字表示太空站（0是地球，n是月球），第二个数字表示的是时间。然后从(i,t-1)到(i,t)连一条容量为INF的边（太空站可以停留无限的人），从地球（超级源点）连一条INF的边到(0,t)，从(n,t)连一条INF的边到月球（超级汇点），然后考虑所有的太空船，设其中一个太空船的移动为a0,a1,a2....aT-1，那么连接一条从(a[(t-1)%T],t-1)到(a[t%T],t)，容量为此太空船容量的边，求最大流，如果最大流的大于了总人数，就跳出，答案就是当前的时间。
详见代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cstdio>
#define MAX_M 201
#define MAX_V 100861
#define INF 10086111
using namespace std; struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
vector<int> ship[MAX_M];
//bool nodeColor[MAX_N];
const int moon=MAX_V-1,earth=MAX_V-2; int N,M,K; int shipCap[MAX_M];
int father[MAX_M]; bool used[MAX_V]; void init()
{
for(int i=0;i<=N+1;i++)father[i]=i;
} int Find(int u)
{
if(father[u]==u)return u;
else return father[u]=Find(father[u]);
} void unionSet(int u,int v)
{
int x=Find(u),y=Find(v);
if(x==y)return;
father[x]=y;
} bool Same(int u,int v)
{
return Find(u)==Find(v);
} bool check()
{
for(int i=0;i<M;i++)
{
int u=ship[i][0];
for(int j=1;j<ship[i].size();j++)
unionSet(u,ship[i][j]);
}
return Same(0,N+1);
} void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
} int dfs(int v,int t,int f)
{
if(v==t)return f;
used[v]=1;
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if(!used[e.to]&&e.cap>0)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
} int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(used,0,sizeof(used));
int f=dfs(s,t,INF);
if(f==0)return flow;
flow+=f;
}
}
char cc;
int flo=0;
int main()
{
cin>>N>>M>>K;
for(int i=0;i<M;i++)
{
cin>>shipCap[i];
int r;
cin>>r;
for(int j=0;j<r;j++)
{
int ss;
cin>>ss;
if(ss==-1)ss=N+1;
ship[i].push_back(ss);
}
} if(!check()){cout<<0<<endl;return 0;} int nowNode=0;
N++;
int ans=0;
//cout<<N<<endl;
//cin>>cc>>cc;
for(int t=0;;t++)
{
for(int i=0;i<=N;i++)
{
int v=i+nowNode;
if(t!=0)
add_edge(v-N-1,v,INF);
if(i==0)
add_edge(earth,v,INF);
if(i==N)
add_edge(v,moon,INF);
}
for(int i=0;i<M&&t!=0;i++)
{
int tt=t%ship[i].size();
int fr=ship[i][(tt-1<0)?(tt-1+ship[i].size()):(tt-1)]+nowNode-N-1;
int go=ship[i][tt]+nowNode;
add_edge(fr,go,shipCap[i]);
}
flo+=max_flow(earth,moon); if(flo>=K){ans=t;break;}
nowNode+=N+1;
/*for(int i=0;i<nowNode;i++)
for(int j=0;j<G[i].size();j++)
cout<<i<<" "<<G[i][j].to<<" "<<G[i][j].cap<<endl;
cout<<flo<<endl;
cout<<"--------"<<endl;
cin>>cc;*/
if(t>100){cout<<0<<endl;return 0;}
}
cout<<ans<<endl;
return 0;
}