[CTSC1999]家园

枚举跑多少天，动态加边即可。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=1000005,inf=0x3f3f3f3f;
int n,m,K,p[50],z[50],g[50][50],fa[50],ans,S,T,head[N],ecnt=1,maxflow,h[N];
struct Edge{int to,nxt,val;}e[N<<1];
void add(int bg,int ed,int val) {e[++ecnt].nxt=head[bg];e[ecnt].to=ed; e[ecnt].val=val; head[bg]=ecnt;swap(bg,ed);e[++ecnt].nxt=head[bg]; e[ecnt].to=ed; e[ecnt].val=0; head[bg]=ecnt;}
bool bfs() {
    memset(h,-1,sizeof h);
    queue<int>q;q.push(S);h[S]=0;
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=head[u]; i; i=e[i].nxt) {
					  int v=e[i].to;if(h[v]==-1&&e[i].val) {h[v]=h[u]+1;q.push(v);}
        }
    }
    return h[T]!=-1;
}
int dfs(int x,int f) {
    if(x==T)return f;
    int used=0,tp;
    for(int i=head[x]; i; i=e[i].nxt) {
        int v=e[i].to;
        if(h[v]-1==h[x]&&e[i].val) {
            tp=dfs(v,min(e[i].val,f-used));
            used+=tp;e[i].val-=tp;e[i^1].val+=tp;
            if(used==f)return f;
        }
    }
    if(used==0)h[x]=-1;
    return used;
}
int main() {
	scanf("%d%d%d",&n,&m,&K);
	S=0,T=N-2;
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&p[i],&z[i]);
		for(int j=1;j<=z[i];j++)
			scanf("%d",&g[i][j-1]),g[i][j-1]=(g[i][j-1]==0)?n+1:((g[i][j-1]==-1)?n+2:g[i][j-1]);
	}
	while(++ans) {
		if(ans>500) return puts("0"),0;
		add(S,(ans)*(n+1),inf);
		for(int i=1,x,y;i<=m;i++) {
			x=(ans-1)%z[i],y=ans%z[i];
			if(g[i][x]==n+2) x=T;
			else x=(ans-1)*(n+1)+g[i][x];
			if(g[i][y]==n+2) y=T;
			else y=(ans)*(n+1)+g[i][y];
			add(x,y,p[i]);
		}
		while(bfs()) maxflow+=dfs(S,inf);
		if(maxflow>=K) {printf("%d",ans);return 0;}
		for(int i=1;i<=n+1;i++) add((ans-1)*(n+1)+i,ans*(n+1)+i,inf);
	}
}