【模板】网络流——Dinic

#include <cstdio> #include <vector> #include <cstring> #define maxn 1000 #define INF 0x3f using namespace std; /* 设在残量网络中节点u到源点s的距离为dist[u] 只保留每个点出发到dist+1的边（边(u,v)存在仅当dist[u]+1=dist[v]） */ struct Edge{ int from,to,cap,flow; }; struct Dinic{ int n,m,s,t;//节点数，边数，源点，汇点 vector<Edge> edges; vector<int> G[maxn]; bool vis[maxn]; int d[maxn];//用来记录层次 int cur[maxn]; bool BFS(){ memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(!vis[e.to] && e.cap>flow){ vis[e.to]=true; d[e.to]=d[x]+1; Q.push(e.to); } }//while内除了遍历cur相连顶点外别无他物 } return vis[t];//先写while，然后直接写return，然后再填while内东西 } int DFS(int x,int a){//x表示当前节点，a表示目前为止所有弧的最小残量 if(x==t || a==0) return a;//如果x是汇点并且残量为0，不必再更新； //要记住写↑这一步 int flow=0; int f; for(int& i=cur[x];i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){ e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int maxFlow(int s,int t){ this->s=s; this->t=t; int flow=0; while(BFS()){ memset(cur,0,sizeof(cur)); flow+=DFS(s,INF); } return flow; } };

转载于:https://www.cnblogs.com/leotan0321/p/6081387.html

相关资源：数据结构—成绩单生成器