CTSC1999家园
建模方法类似我NOI2019网络同步赛我的T1写法[【题解】NOI2019Route]（70分）
问题的焦点是：空间时间载具。
考虑如何击破时间限制，可以对每个点关于每个时刻建立一个点，这样就实现一个点在两个时间互不干扰。由于时间是流淌的，所以从过去到现在连一条免费的\(inf\)边
此时空间问题也就解决了，比较空间就是具体的节点。
考虑载具，载具就相当于一个时刻在新建边的东西，我们直接枚举时间让他慢慢加点就好了。注意到载具总要从上个时间连接到这个时间，相当于虫洞？
下面这个图会非常清楚：
写的话有点麻烦，模块化编程就稍微好写点。数据范围不超过100，不用怕MLE,TLE。
发现一种很好用的调试技巧，就是在add函数中输出fr to w 等等内容，按照这个提示建图就可以很快发现问题。
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; typedef long long ll;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(c<48||c>57)f|=c==45,c=getchar();
while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=5e4+5;
struct E{
int to,nx,w;
E(){to=nx=w=0;}
E(const int&a,const int&b,const int&c){to=a;nx=b;w=c;}
}e[maxn];
int head[maxn];
int last[maxn];
int lastlast[maxn];
int cnt=1;
int n,m,k;
int nodecnt;
int S,T;
const int inf=0x3f3f3f3f;
inline void add(const int&fr,const int&to,const int&w,const int&f=1){
e[++cnt]=E(to,head[fr],w);
head[fr]=cnt;
if(f) add(to,fr,0,0);
}
queue < int > q;
int d[maxn],cur[maxn];
inline bool bfs(){
for(register int t=1;t<=nodecnt;++t) d[t]=0,cur[t]=head[t];
d[S]=1;q.push(S);
while(q.size()){
register int now=q.front();
q.pop();
//cout<<"now="<<now<<' '<<T<<endl;
for(register int t=head[now];t;t=e[t].nx){
if(e[t].w>0&&d[e[t].to]==0){
d[e[t].to]=d[now]+1;
q.push(e[t].to);
}
}
}
return d[T];
}
int dfs(const int&now,int fl){
if(now==T||fl==0)return fl;
register int ret=0;
for(register int&t=cur[now];t;t=e[t].nx){
if(e[t].w>0&&d[e[t].to]==d[now]+1){
int d=dfs(e[t].to,min(e[t].w,fl));
e[t].w-=d;e[t^1].w+=d;ret+=d;fl-=d;
}
}
return ret;
}
inline int dinic(){
register int ret=0;
while(bfs()) ret+=dfs(S,inf);
return ret;
}
int sh[205][205];
int siz[205];
int stay[205];
int cap[205];
inline void init(){
S=++nodecnt;
T=++nodecnt;
for(register int t=1;t<=n+2;++t) last[t]=++nodecnt;
add(S,last[n+1],k);
}
inline void update(const int&now){
for(register int t=1;t<=n+2;++t)
add(lastlast[t]=last[t],++nodecnt,inf),last[t]=nodecnt;
for(register int t=1;t<=m;++t){
int la=stay[t];
int to=(stay[t]+1)%siz[t];
add(lastlast[sh[t][la]],last[sh[t][to]],cap[t]);
stay[t]=to;
}
add(last[n+2],T,inf);
}
namespace binc{
int r[201];
int n;
inline void init(int a){n=a;for(int t=1;t<=n;++t) r[t]=t;}
int q(int a){return a==r[a]?a:r[a]=q(r[a]);}
void j(int a,int b){r[q(a)]=q(b);}
}
int main(){
n=qr();m=qr();k=qr();
binc::init(n+2);
for(register int t=1;t<=m;++t){
cap[t]=qr();
siz[t]=qr();
for(register int i=0;i<siz[t];++i){
sh[t][i]=qr();
if(sh[t][i]==0)sh[t][i]=n+1;
if(sh[t][i]==-1)sh[t][i]=n+2;
if(i)binc::j(sh[t][i],sh[t][i-1]);
}
}
if(binc::q(n+1)!=binc::q(n+2)) return puts("0"),0;
int timenow=0,sum=0,t1,cnt=0;
init();
while(sum<k){
update(++timenow);
t1=dinic();
sum+=t1;
if(t1==0&&sum)++cnt;
}
printf("%d\n",timenow);
return 0;
}