Description
由于人类对自然资源的消耗，人们意识到大约在$2300$年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，$2177$年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有$n$个太空站位于地球与月球之间，且有$m$艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船$i$只可容纳$H_i$个人。每艘太空船将周期性地停靠一系列的太空站，
例如：$(1,3,4)$表示该太空船将周期性地停靠太空站$134134134...$。每一艘太空船从一个太空站驶往任一太空站耗时均为$1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。
初始时所有人全在地球上，太空船全在初始站。求让所有人全部转移到月球上所需最短用时。
Input
第$1$行有$3$个正整数$n$(太空站个数)，$m$(太空船个数)和$k$(需要运送的地球上的人的个数)。
接下来的$m$行给出太空船的信息。第$i+1$行说明太空船$p_i$。第$1$个数表示$p_i$可容纳的人数$H_i$；第$2$个数表示$p_i$一个周期停靠的太空站个数$r_i$；随后$r_i$个数是停靠的太空站的编号:$S_{i,1},S_{i,2},...,S_{i,r}$，地球用$0$表示，月球用$-1$表示。时刻$0$时，所有太空船都在初始站，然后开始运行。在时刻$1,2,3...$等正点时刻各艘太空船停靠相应的太空站。人只有在$0,1,2...$等正点时刻才能上下太空船。
Output
一行一个整数,表示将全部人员安全转移所需最短用时。如果问题无解，则输出$0$。
Sample Input
2 2 1
1 3 0 1 2
1 3 1 2 –1
Sample Output
5
HINT
$1;leq;m;leq;13,1;leq;n;leq;20,1;leq;k;leq;50,1;leq;r;leq;n+2$.Solution
遍历判断从地球到月球是否存在一条路径,若不存在,则无解.
将每个点按时间拆成$d$个点,$x_{i,d}$表示第$i$个太空站第$d$天的情况.
顺序枚举答案$d$.
从$s$到$x_{0,d}$连一条容量为$+infty$的有向边,
从$x_{-1,d}$到$t$连一条容量为$+infty$的有向边,
从$x_{i,d-1}$到$x_{i,d}$连一条容量为$+infty$的有向边,
若存在某艘太空船$k$,第$d-1$天在$i$,第$d$天在$j$,从$x_{i,d-1}$到$x_{j,d}$连一条容量为$H_k$的有向边.
求最大流,若流量$;leq;k$,则$d$为答案.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 25 #define K 1105 #define M 77005 using namespace std; struct graph{ int nxt,to,f; }e[M],e1[K]; int a[N][N],h[N],r[N],g[K],g1[N],dep[K],n,m,k,s,t,fl,tot,cnt; bool v[N]; queue<int> q; inline void added(int x,int y){ e1[++cnt].nxt=g1[x];g1[x]=cnt;e1[cnt].to=y; } inline void addedge(int x,int y,int f){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].f=f; } inline void adde(int x,int y,int f){ addedge(x,y,f);addedge(y,x,0); } inline int f(int d){ return tot*d; } inline bool bfs(int u){ memset(dep,0,sizeof(dep)); q.push(u);dep[u]=1; while(!q.empty()){ u=q.front();q.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f>0&&!dep[e[i].to]){ q.push(e[i].to); dep[e[i].to]=dep[u]+1; } } return dep[t]; } inline int dfs(int u,int f){ int ret=0; if(u==t) return f; for(int i=g[u],d;i&&f;i=e[i].nxt) if(e[i].f>0&&dep[e[i].to]>dep[u]){ d=dfs(e[i].to,min(f,e[i].f)); ret+=d;f-=d;e[i].f-=d;e[i^1].f+=d; } return ret; } inline int dinic(){ int ret=0; while(true){ if(!bfs(s)) return ret; ret+=dfs(s,M); } } inline bool chk(int u){ v[u]=true;q.push(u); while(!q.empty()){ u=q.front();q.pop(); for(int i=g1[u];i;i=e1[i].nxt) if(!v[e1[i].to]){ if(e1[i].to==n+2) return true; q.push(e1[i].to);v[e1[i].to]=true; } } return false; } inline void Aireen(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;++i){ scanf("%d%d",&h[i],&r[i]); for(int j=0;j<r[i];++j){ scanf("%d",&a[i][j]); if(!a[i][j]) a[i][j]=n+1; else if(a[i][j]<0) a[i][j]=n+2; } for(int j=1;j<r[i];++j) added(a[i][j-1],a[i][j]); if(r[i]>1) added(a[i][r[i]-1],a[i][0]); } if(!chk(n+1)){ puts("0");return; } s=0;t=K-1;tot=n+2;cnt=1; adde(0,n+1,M);adde(n+2,t,M); for(int d=1;;++d){ adde(s,n+1+f(d),M);adde(n+2+f(d),t,M); for(int i=1;i<=n;++i) adde(i+f(d-1),i+f(d),M); for(int i=1;i<=m;++i) adde(a[i][(d-1)%r[i]]+f(d-1),a[i][d%r[i]]+f(d),h[i]); fl+=dinic(); if(fl>=k){ printf("%d ",d);return; } } } int main(){ freopen("home.in","r",stdin); freopen("home.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }