struct edge { int to,flow,next; }; int head[MAXN],cnt,Dep[MAXN],cur[MAXN]; edge Gra[MAXN*4]; void addEdge(int st,int en,int val)///如果是双向边的话注意两条边都是val,单向边建立反向0边 { Gra[cnt].flow=val; Gra[cnt].to=en; Gra[cnt].next=head[st]; head[st]=cnt++; } void prework() { memset(head,-1,sizeof(head)); cnt=0; } bool bfs()///分层次 { queue<int>que; while(!que.empty())que.pop(); memset(Dep,0,sizeof(Dep)); Dep[St]=1; que.push(St); while(!que.empty()) { int u=que.front(); que.pop(); for(int i=head[u];i!=-1;i=Gra[i].next) { int v=Gra[i].to; if(Gra[i].flow>0&&Dep[v]==0) Dep[v]=Dep[u]+1,que.push(v); } } if(Dep[En]!=0)///是否有一条非0边通向终点 return true; return false; } int dfs(int u,int flow)///直接增广的思想 { if(u==En) return flow; for(int &i=cur[u];i!=-1;i=Gra[i].next)///注意&传引用,弧优化的重点 { int v = Gra[i].to; if(Dep[v]==Dep[u]+1&&Gra[i].flow!=0) { int tmp=dfs(v,min(flow,Gra[i].flow)); if(tmp>0) { Gra[i].flow-=tmp; Gra[i^1].flow+=tmp;///如果是双向的+变- return tmp; } } } return 0; } int Dinic() { int ans=0; while(bfs()) { for(int i=St;i<=En;i++)///弧优化的前置处理 cur[i]=head[i]; while(int tmp=dfs(St,inf))///重要的优化时间的点 ans+=tmp; } return ans; }