题目来源 : https://www.luogu.org/problemnew/show/P2754
由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有 n 个太空站位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站 134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。
初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。
对于给定的太空船的信息，找到让所有人尽快地全部转移到月球上的运输方案。
输入输出格式
输入格式：
第 1 行有 3 个正整数 n（太空站个数），m（太空船个数）和 k（需要运送的地球上的人的个数）。其中 n<=13 m<=20, 1<=k<=50。
接下来的 m 行给出太空船的信息。第 i+1 行说明太空船 pi。第 1 个数表示 pi 可容纳的人数 Hpi；第 2 个数表示 pi 一个周期停靠的太空站个数 r，1<=r<=n+2；随后 r 个数是停靠的太空站的编号(Si1,Si2,…,Sir)，地球用 0 表示，月球用-1 表示。
时刻 0 时，所有太空船都在初始站，然后开始运行。在时刻 1，2，3…等正点时刻各艘太空船停靠相应的太空站。人只有在 0,1,2…等正点时刻才能上下太空船。
输出格式：
程序运行结束时，将全部人员安全转移所需的时间输出。如果问题
无解，则输出 0。
输入输出样例
输出样例#1：
5
emmmmm，做了几道网络流的题，发现我还是不会建图,一做题就感觉不是时间爆炸，就是图不成立，在不就空间爆炸，说到底就是建不出图，哎，努力学习建图
这道题的建图思路可以想到的，虽然说比较难想(反正我这个菜鸡是没有想到)，每一个点有两个意义，第一是这个点代表的位置，第二是时刻，意思就是每点都是在某个时间上的某个点，说的有点乱
意思就是这个意思吧，之后起点连接下一个时间的终点（时间恒为1），我连接时汇点为月球，原点为0（不是地球），地球有时间概念，每个地球都和源点相连，这样大致的图就出来了，只要考虑一一下滞留
问题图就已经没问题了，所谓的滞留就是这个（时间为t的x点）会转移到下一个时间点（时间为t+1的点x）上，很容易理解，但是想不到，好难受。
还有就是这题我在洛谷上写的 第六个点不知道wa在哪，希望大佬留步指点一下，还有就是感觉思路和代码有什么问题的也希望可以告诉我一下，orz感谢大佬们
#include<bits/stdc++.h> using namespace std; #define INT_MAX 0x73f3f3f const int maxn = 2e5+10; struct edge{ int eend; int weight; int next; }x[maxn]; int head[maxn]; int cnt; int bing[maxn]; typedef struct w_W{ int weight; int ge; int f[500]; int start[500]; int eend[500]; }miao; miao chuan[500]; int ceng[maxn]; queue<int> q1; int Find(int a){ if(a==bing[a]) return bing[a]; return bing[a]=Find(bing[a]); } void add(int a,int b,int c){ x[cnt].eend=b; x[cnt].weight=c; x[cnt].next=head[a]; head[a]=cnt++; x[cnt].eend=a; x[cnt].weight=0; x[cnt].next=head[b]; head[b]=cnt++; } int bfs(int start,int eend){ memset(ceng,0,sizeof(ceng)); ceng[start]=1; q1.push(start); while(q1.size()){ int dang=q1.front(); q1.pop(); for(int i=head[dang];i!=-1;i=x[i].next){ int to=x[i].eend; if(ceng[to]==0&&x[i].weight>0){ ceng[to]=ceng[dang]+1; q1.push(to); } } } if(ceng[eend]==0) return 0; else return 1; } int dfs(int dang,int eend,int xiao){ if(dang==eend) return xiao; for(int i=head[dang];i!=-1;i=x[i].next){ int to=x[i].eend; if(ceng[to]==ceng[dang]+1&&x[i].weight>0){ int dd=dfs(to,eend,min(xiao,x[i].weight)); if(dd>0){ x[i].weight-=dd; x[i^1].weight-=dd; return dd; } } } return 0; } int main() { int m,n,k; cnt=0; scanf("%d %d %d",&n,&m,&k); memset(head,-1,sizeof(head)); for(int i=0;i<=n+2;i++) bing[i]=i; for(int i=0;i<m;i++){ scanf("%d",&chuan[i].weight); scanf("%d",&chuan[i].ge); for(int j=0;j<chuan[i].ge;j++){ scanf("%d",&chuan[i].f[j]); if(chuan[i].f[j]==-1) chuan[i].f[j]=n+1; if(chuan[i].f[j]==0) chuan[i].f[j]=n+2; } int ha=0; chuan[i].start[ha]=chuan[i].f[chuan[i].ge-1]; chuan[i].eend[ha]=chuan[i].f[0]; ha++; for(int j=1;j<chuan[i].ge;j++){ chuan[i].start[ha]=chuan[i].f[j-1]; chuan[i].eend[ha]=chuan[i].f[j]; ha++; } } for(int i=0;i<m;i++){ for(int j=0;j<chuan[i].ge;j++){ int f1=Find(chuan[i].start[j]),f2=Find(chuan[i].eend[j]); if(f1!=f2) bing[f1]=f2; } } if(Find(n+2)!=Find(n+1)){ printf("0 "); return 0; } int maxx=0; int t=1; while(1){ //system("pause"); add(0,(n+2)+(t-1)*(n+3),INT_MAX); for(int i=0;i<m;i++){ for(int j=0;j<chuan[i].ge;j++){ if(t%chuan[i].ge==j){ if(chuan[i].start[j]!=n+1&&chuan[i].eend[j]!=n+1){ add(chuan[i].start[j]+(t-1)*(n+3),chuan[i].eend[j]+(t)*(n+3),chuan[i].weight); //if(chuan[i].start[j]!=n+2) add(chuan[i].start[j]+(t-1)*(n+3),chuan[i].start[j]+(t)*(n+3),INT_MAX); //printf("%d %d ",chuan[i].start[j]+(t-1)*(n+3),chuan[i].eend[j]+(t)*(n+3)); } else if(chuan[i].start[j]==n+1){ add(n+1,chuan[i].eend[j]+(t)*(n+3),chuan[i].weight); //printf("%d %d ",n+1,chuan[i].eend[j]+(t)*(n+3)); } else{ add(chuan[i].start[j]+(t-1)*(n+3),n+1,chuan[i].weight); // printf("%d %d ",chuan[i].start[j]+(t-1)*(n+3),n+1); //if(chuan[i].start[j]!=n+2) add(chuan[i].start[j]+(t-1)*(n+3),chuan[i].start[j]+(t)*(n+3),INT_MAX); } } } } while(bfs(0,n+1)){ int ha=dfs(0,n+1,INT_MAX); if(ha>0) maxx+=ha; } if(maxx>=k) break; for(int i=1;i<=n+2;i++){ //if(i==n+1) continue; add(i+(t-1)*(n+3),i+t*(n+3),INT_MAX); } t++; } printf("%d ",t); return 0; }