[CTSC1999] 家园

使用并查集判断无解。

令月球是n+1，地球是0

枚举时长t，将点（地球、月球以及太空站）i拆为t个点(i,j)表示第j时刻的点i。

对于太空船云云建图，容量是h[i]。

源点S和(0,0)连边，容量k。

(n+1,*)和汇点连边，容量k。

跑最大流，判断其是否≥k。

每一次答案可以考虑利用残余网络，虽然有点麻烦就是了。。

代码里没写UFS。。懒得了。。

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N=5e4+5;

const int L=5e6+5;

const int inf=0x3f3f3f3f;

int S=N-1,T=N-2;

int head[N],to[L],upp[L],last[L],cnt=1;

int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int u) {

	to[++cnt]=y,upp[cnt]=u,last[cnt]=head[x],head[x]=cnt;

	to[++cnt]=x,upp[cnt]=0,last[cnt]=head[y],head[y]=cnt;

}

inline bool bfs() {

	memset(lev,0,sizeof lev);

	lev[S]=1;

	que[hd=0,tl=1]=S;

	while(hd<tl) {

		int x=que[++hd];

		for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]])

			lev[to[i]]=lev[x]+1, que[++tl]=to[i];

	}

	return lev[T]!=0;

}

int dfs(int x,int tf) {

	if(x==T) return tf;

	int tot=0,tmp;

	for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {

		tmp=dfs(to[i],min(tf-tot,upp[i]));

		if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;

		if(tot==tf) break;

	}

	if(!tot) lev[x]=-1;

	return tot;

}

int n,m,k;

int h[N];

vector<int> a[N];

inline int I(int x,int t) { return t*(n+2)+x+1;}

int main() {

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1,k,x; i<=m; ++i) {

		scanf("%d%d",h+i,&k);

		while(k--) {

			scanf("%d",&x);

			if(x==-1) x=n+1;

			a[i].push_back(x);

		}

	}

	int ans=0;

	for(int t=0; t<=500; ++t) {

		add_edge(S,I(0,t),inf);

		add_edge(I(n+1,t),T,inf);

		if(t) {

			for(int i=1; i<=m; ++i) {

				int x=a[i][(t-1)%a[i].size()];

				int y=a[i][t%a[i].size()];

				add_edge(I(x,t-1),I(y,t),h[i]);

			}

			for(int i=1; i<=n; ++i) {

				add_edge(I(i,t-1),I(i,t),inf);

			}

		}

		while(bfs()) ans+=dfs(S,inf);

		if(ans>=k) {

			printf("%d\n",t);

			return 0;

		}

	}

	printf("0");

	return 0;

}