nbu 2431 星际转移问题

题目链接：http://acm.nbu.edu.cn/v1.0/Problems/Problem.php?pid=2431

题目大意：

中文题意，不解释。

题目思路：

源自王晓东《线性规划和网络流24题》。

原题的解法，一种枚举答案+动态建图，一种二分答案+多次建图，因为原题最多30天。

但是这题最多可以是1000多天，所以二分答案+多次建图会TLE。

不过两种解法的思路基本一致，但是第一种解法，每次求出来的最大流并不是能把多少人送到月球，而是比前一天能多送几人到月球。

建图：

设（x，day）表示第day天的x空间站（0：地球）。

（1）首先建立一个超级源点S ---〉（0，0），容量为k（要运送的人），汇点T为月球。

（2）设为第day天，则对所有i（0~n）建立（i，day-1） ---〉（i，day），容量为正无穷大，因为一个空间站可以容量任意多人。

（3）设为第day天，设有一飞船从u飞到v，则建立（u，day-1） ---〉 （v，day），如果v为月球，则建立（u，day-1）---〉T，容量为该飞船最大运载人数。

解释：

建图（1）保证网络中的流量不会超过k。

建图（2），（3）使得day天前的信息与day天相联系。

用sap的同学请注意啦，如果之前不先用bfs（）来初始化dis[]]数组的话很有可能超时的。

因为sap为了写得更简洁，通常直接用memset（）来初始化dis[]使其均为0，利用sap自身的回退来寻找增广路，但是对于这题，增加一天无增广路的几率极大，所以都只用sap的回退来找增广路代价是很大的，所以bfs（）先判断是否有合法路径效率就高多了，而且这样才能更充分利用前面的信息。

ps：个人觉得第一种方法可能是作者的原意，该题相当于把该网络按照天数分层了，而动态建图也正是如此。

代码：

#include <stdlib.h>#include <string.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <string>#include <iostream>#include <algorithm>using namespace std;#define ll __int64#define ls rt<<1#define rs ls|1#define lson l,mid,ls#define rson mid+1,r,rs#define middle (l+r)>>1#define eps (1e-8)#define clr_all(x,c) memset(x,c,sizeof(x))#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))#define MOD 1000000009#define INF 0x3f3f3f3f#define PI acos(-1.0)template <class T> T _abs(T x){return (x>0)? x:-x;}template <class T> T _max(T x,T y){return (x>y)? x:y;}template <class T> T _min(T x,T y){return (x<y)? x:y;}template <class T> void getmax(T &x,T y){x= (x>y)? x:y;}template <class T> void getmin(T &x,T y){x= (x!=-1 && x<y)? x:y;}template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}int TS,cas=1;const int M=50000+5;int n,m,k;int h[55],r[55],s[55][55];int maze[55][55],inq[55];struct sap{typedef int type;struct edge{int to,next;type flow;}edg[999999];int n,m;int g[M],cur[M],pre[M];int dis[M],gap[M];int q[M],head,tail;void init(int _n){n=_n,m=0,clr_all(g,-1);}void insert(int u,int v,type f,type c=0){edg[m].to=v,edg[m].flow=f,edg[m].next=g[u],g[u]=m++;edg[m].to=u,edg[m].flow=0,edg[m].next=g[v],g[v]=m++;}bool bfs(int s,int t){clr(gap,0,n),clr(dis,-1,n);gap[dis[t]=0]++,dis[s]=-1;for(q[head=tail=0]=t;head<=tail;){int u=q[head++];for(int i=g[u];i!=-1;i=edg[i].next){edge& e=edg[i],ee=edg[i^1];if(dis[e.to]==-1 && ee.flow>0){gap[dis[e.to]=dis[u]+1]++;q[++tail]=e.to;}}}return dis[s]!=-1;}type maxFlow(int s,int t){if(!bfs(s,t)) return 0;type res=0,a;int i;for(i=0;i<n;i++) cur[i]=g[i];pre[s]=s,cur[s]=g[s],cur[t]=g[t];for(int u=s;dis[s]<n;){if(u==t){for(a=-1;u!=s;u=pre[u])getmin(a,edg[cur[pre[u]]].flow);for(u=t;u!=s;u=pre[u]){edg[cur[pre[u]]].flow-=a;edg[cur[pre[u]]^1].flow+=a;}res+=a;}bool ok=0;for(i=cur[u];i!=-1;i=edg[i].next){edge& e=edg[i];if(dis[u]==dis[e.to]+1 && e.flow>0){cur[u]=i,pre[e.to]=u,u=e.to;ok=1;break;}}if(ok) continue;int mindis=n-1;for(i=g[u];i!=-1;i=edg[i].next){edge& e=edg[i];if(mindis>dis[e.to] && e.flow>0)mindis=dis[e.to],cur[u]=i;}if(--gap[dis[u]]==0) break;gap[dis[u]=mindis+1]++,u=pre[u];}return res;}}p;int cal(int i,int x){return (i>n)? M-1:i+(n+1)*x;}bool bfs(int s){queue<int>q;clr_all(inq,0);q.push(s),inq[s]=1;while(!q.empty()){s=q.front(),q.pop();for(int i=0;i<n+2;i++) if(maze[s][i] && !inq[i]){if(i==n+1) return true;q.push(i),inq[i]=1;}}return false;}void run(){int i,j;clr_all(maze,0);for(i=1;i<=m;i++){scanf("%d%d",&h[i],&r[i]);for(j=0;j<r[i];j++){scanf("%d",&s[i][j]);if(s[i][j]==-1) s[i][j]=n+1;}for(j=1;j<r[i];j++)maze[s[i][0]][s[i][j]]=maze[s[i][j]][s[i][0]]=1;}if(bfs(0)){p.init(n+1+2);int soc=M-2,tar=M-1;p.insert(soc,0,k);int sum=0;for(i=1;i<=2000;i++){p.n+=n+2;for(j=0;j<=n;j++)p.insert(cal(j,i-1),cal(j,i),INF);for(j=1;j<=m;j++){int from=s[j][(i-1)%r[j]],to=s[j][i%r[j]];p.insert(cal(from,i-1),cal(to,i),h[j]);}if((sum+=p.maxFlow(soc,tar))==k){printf("%d\n",i);return;}}}puts("0");}void preSof(){}int main(){    //freopen("input.txt","r",stdin);    //freopen("output.txt","w",stdout);    preSof();    //run();    while(~scanf("%d%d%d",&n,&m,&k)) run();    //for(scanf("%d",&TS);cas<=TS;cas++) run();    return 0;}