【codevs1034】星际转移问题（家园）（网络流）

星际转移问题（家园）（网络流）"/>

【codevs1034】星际转移问题（家园）（网络流）

题目：
我是超链接
题解：
建图如下

枚举时间点，因为飞船在跑，由st[i][t]到st[next[i]][t+1]连边
人们也可以蹲在太空站里，st[i][t]到st[i][t+1]连边
然后就是最大流啦
代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#define INF 1e9
using namespace std;
int p[55],tim,deep[50005],point[50005],cur[50005],tot=-1,r[55][55],next[50005],v[50005],remind[50005];
int n,m,k;
void addline(int x,int y,int cap)
{++tot; next[tot]=point[x]; point[x]=tot; v[tot]=y; remind[tot]=cap;++tot; next[tot]=point[y]; point[y]=tot; v[tot]=x; remind[tot]=0;
}
int addflow(int t,int now,int limit)
{if (!limit||now==t) return limit;int f=0,flow=0;for (int i=cur[now];i!=-1;i=next[i]){cur[now]=i;if (deep[v[i]]==deep[now]+1 && (f=addflow(t,v[i],min(remind[i],limit)))){flow+=f;limit-=f;remind[i]-=f;remind[i^1]+=f;if (!limit) break;}}return flow;        
}
bool bfs(int s,int t)
{queue <int> q;q.push(s);memset(deep,0x7f,sizeof(deep));deep[s]=0;while (!q.empty()){int now=q.front();q.pop();for (int i=point[now];i!=-1;i=next[i])if (remind[i] && deep[v[i]]>INF){deep[v[i]]=deep[now]+1;q.push(v[i]);}}if (deep[t]<INF) for (int i=1;i<=m*tim;i++) cur[i]=point[i];cur[s]=point[s]; cur[t]=point[t];return deep[t]<INF;
}
int main()
{int i,j;memset(point,-1,sizeof(point));memset(next,-1,sizeof(next));scanf("%d%d%d",&n,&m,&k);for (i=1;i<=m;i++){scanf("%d%d",&p[i],&r[i][0]);for (j=1;j<=r[i][0];j++){scanf("%d",&r[i][j]);if (r[i][j]<=0) r[i][j]+=5000;          }}int s=5000,t=4999,we=0;tim=0;  while ((++tim)<=600){for (i=1;i<=m;i++){int x,y;if (r[i][(tim-1)%r[i][0]+1]==s) x=s;else if (r[i][(tim-1)%r[i][0]+1]==t) x=t;else x=(tim-1)*n+r[i][(tim-1)%r[i][0]+1];if (r[i][tim%r[i][0]+1]==s) y=s;else if (r[i][tim%r[i][0]+1]==t) y=t;else  y=tim*n+r[i][tim%r[i][0]+1];addline(x,y,p[i]);}for (i=1;i<=n;i++) addline((tim-1)*n+i,(tim-1)*n+i+n,INF);while (bfs(s,t)) we+=addflow(t,s,INF);if (we>=k){printf("%d",tim); return 0;}}printf("0");
}