太菜了，一个地方打错调试3个小时qwq
新技巧get
分层图网络流
/*
@Date : 2019-07-18 09:27:30
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
const int inf=2147483647;
const int M=10000000+7;
const int N=10000+7;
struct edge{
int v,nxt,flow;
}e[M<<1];
#define S 0
#define T (M-1)
int head[M],cnt;
inline void add(int u,int v,int f){e[cnt]=(edge){v,head[u],f},head[u]=cnt++;}
inline void link(int u,int v,int f){add(u,v,f);add(v,u,0);}
inline void init(void){cnt=0;memset(head,-1,sizeof head);}
int n,m,people,fa[N];
int H[N];
int g[100][100],num[100];
inline int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}
inline void merge(int x,int y){if((x=find(x))^(y=find(y)))fa[x]=y;}
inline bool check(int x,int y){return find(x)==find(y);}
inline int id(int time,int point){return (time-1)*(n+1)+point;}//hash
int dep[M];
int ans,maxflow;
inline bool bfs()
{
memset(dep,0,sizeof dep);
// dep[T]=0;
static int Q[N<<1];
int l=0,r=0;
dep[Q[l=r=0]=S]=1;
while(l<=r)
{
int p=Q[l++];
// cout<<"p="<<p<<endl;
if(p==T)return true;
for(int i=head[p];~i;i=e[i].nxt)
if(e[i].flow&&!dep[e[i].v])
dep[e[i].v]=dep[p]+1,Q[++r]=e[i].v;
}
return false;
}
inline int dfs(int p,int restflow)
{
if(p==T||restflow==0)return restflow;
int sumflow=0;
for(int i=head[p],flow;~i;i=e[i].nxt)
{
int v=e[i].v;
if(e[i].flow&&dep[v]==dep[p]+1&&(flow=dfs(v,min(restflow,e[i].flow))))
{
restflow-=flow,sumflow+=flow;
e[i].flow-=flow,e[i^1].flow+=flow;
if(restflow==0)break;
}
}
return sumflow;
}
void dinic()
{
while(bfs())maxflow+=dfs(S,inf);
}
int main(void)
{
#ifndef ONLINE_JUDGE
File("file");
#endif
n=gi,m=gi,people=gi;
int earth=n+1,moon=n+2;
init();
for(int i=1;i<=n+3;++i)fa[i]=i;
for(int i=1;i<=m;++i)
{
H[i]=gi,num[i]=gi;
for(int j=0;j<num[i];++j)
{
g[i][j]=gi;
if(g[i][j]==-1)g[i][j]=moon;
if(g[i][j]==0)g[i][j]=earth;
if(j)merge(g[i][j-1],g[i][j]);
}
}
if(!check(moon,earth))return pi(ans),0;
while(++ans)
{
link(S,id(ans,earth),inf);
for(int i=1;i<=m;++i)
{
int x=(ans-1)%num[i],y=ans%num[i];
x=(g[i][x]==moon)?T:id(ans,g[i][x]);
y=(g[i][y]==moon)?T:id(ans+1,g[i][y]);
link(x,y,H[i]);
}
dinic();
if(maxflow>=people)return pi(ans),0;
for(int i=1;i<=n+1;++i)link(id(ans,i),id(ans+1,i),inf);
}
return 0;
}原文：https://www.cnblogs.com/LLCSBlog/p/11207812.html