题目链接：https://www.luogu.org/problemnew/show
这是一道分层图最大流问题
样例的分层图大概长这样↓
按时间分层，连边，跑最大流即可，dinic利用残量网络可以跑得更快一些。
对于无解的判断可以用并查集。
上代码↓
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF=2e9; int n,m,s,t,np=1,p,mfl; int l[21][21],f[21],h[5005],cur[5005],tp[5005],q[50050]; struct rpg{ int li,nx,ln; }a[50050]; void add(int ls,int nx,int ln){ a[++np]=(rpg){h[ls],nx,ln}; h[ls]=np; a[++np]=(rpg){h[nx],ls,0}; h[nx]=np; } int find(int x){ if(f[x]==x) return x; else return f[x]=find(f[x]); }void un(int a,int b){ int fa=find(a),fb=find(b); if(fa!=fb) f[fa]=fb; } bool bfs(int ps){ memset(tp,0,sizeof(tp)); int hd=1,tl=1; q[hd]=s; tp[s]=1; while(hd<=tl){ int nw=q[hd++]; for(int i=h[nw];i;i=a[i].li){ if(a[i].ln&&!tp[a[i].nx]){ tp[a[i].nx]=tp[nw]+1; q[++tl]=a[i].nx; } } }return tp[t]; } int dfs(int u,int maxn){ if(u==t||!maxn) return maxn; int sum=0; for(int& i=cur[u];i;i=a[i].li){ if(a[i].ln&&tp[a[i].nx]==tp[u]+1){ int f=dfs(a[i].nx,min(maxn,a[i].ln)); if(f){ maxn-=f; sum+=f; a[i].ln-=f; a[i^1].ln+=f; if(!maxn) break; } } }return sum; } void dnc(int ps){ while(bfs(ps)){ for(int i=0;i<=ps;++i) cur[i]=h[i]; while(int d=dfs(s,INF)) mfl+=d; } } int main(){ scanf("%d%d%d",&n,&l[0][0],&p);t=n+1; for(int i=1;i<=n+1;++i) f[i]=i; for(int i=1;i<=l[0][0];++i){ scanf("%d%d",&l[0][i],&l[i][0]); for(int j=1;j<=l[i][0];++j){ scanf("%d",&l[i][j]); if(l[i][j]==-1) l[i][j]=n+1; if(j>1) un(l[i][j],l[i][j-1]); } }if(find(0)!=find(n+1)){ puts("0"); return 0; } for(int ti=1;;++ti){ for(int i=0;i<=n;++i){ add(i+(ti-1)*(n+2),i+ti*(n+2),INF); }add(n+1+ti*(n+2),n+1+(ti-1)*(n+2),INF); for(int i=1;i<=l[0][0];++i){ int tmp=(ti-1)%l[i][0]+1; add(l[i][tmp]+(ti-1)*(n+2),l[i][ti%l[i][0]+1]+ti*(n+2),l[0][i]); } dnc((ti+1)*(n+2)); if(mfl>=p){ printf("%d\n",ti); return 0; } }return 0; }