洛谷.2754.星际转移问题(最大流Dinic 分层)

题目链接

枚举时间

每一个时间点 对于每个之前的位置像当前位置连边，表示这一时刻可待在原地

每艘船 之前时刻位置向当前时刻连边

注意别漏了0时刻src连向earth的边

#include<cstdio>

#include<cctype>

#include<algorithm>

#define gc() getchar()

const int T=501,N=17*T,M=25*T,INF=1e7;

int n,m,k,src,des,v[25],num[25],pos[25][20];

int Enum,H[N],nxt[M<<1],to[M<<1],cap[M<<1],q[N],lev[N],cur[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline void AddEdge(int u,int v,int w)

{

	to[++Enum]=v, nxt[Enum]=H[u], cap[Enum]=w, H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], cap[Enum]=0, H[v]=Enum;

}

bool BFS(int mx)//这个上界别搞错。。

{

	for(int i=0;i<=mx;++i) lev[i]=0,cur[i]=H[i];

	lev[des]=0;//, cur[des]=H[des];

	lev[src]=1, q[0]=src;

	int h=0,t=1;

	while(h<t)

	{

		int x=q[h++];

		for(int i=H[x];i;i=nxt[i])

			if(!lev[to[i]] && cap[i])

			{

				lev[to[i]]=lev[x]+1, q[t++]=to[i];

				if(to[i]==des) return 1;

			}

	}

	return 0;

}

int Dinic(int u,int flow)

{

	if(u==des) return flow;

	int used=0;

	for(int &i=cur[u];i;i=nxt[i])

		if(lev[to[i]]==lev[u]+1 && cap[i])

		{

			int delta=Dinic(to[i],std::min(cap[i],flow-used));

			if(delta)

			{

				cap[i]-=delta, cap[i^1]+=delta, used+=delta;

				if(used==flow) return flow;

			}

		}

	lev[u]=0;

	return used;

}

int main()

{

	n=read()+2,m=read(),k=read();

	Enum=1, src=0, des=7501;

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

	{

		v[i]=read(), num[i]=read();

		for(int j=0;j<num[i];++j)

		{

			pos[i][j]=read();

			if(!pos[i][j]) pos[i][j]=n-1;

			else if(pos[i][j]==-1) pos[i][j]=n;

		}

	}

	int res=0,tot=0;

	AddEdge(src,n-1,INF);//,AddEdge(n,des,INF);

	while(++res<500)

	{

		AddEdge(src,res*n+n-1,INF), AddEdge(res*n+n,des,INF);

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

			AddEdge((res-1)*n+i,res*n+i,INF);

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

			AddEdge((res-1)*n+pos[i][(res-1)%num[i]],res*n+pos[i][res%num[i]],v[i]);

		while(BFS((res+1)*n)) tot+=Dinic(src,INF);

		if(tot>=k) break;

	}

	if(res==500) putchar('0');

	else printf("%d",res);

    return 0;

}