洛谷.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;
}

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

相关推荐