//定义一个名为F的网络流:NetWorkFlow F(n,S,T); //复杂度V^2*E struct NetWorkFlow { struct Flownode { int vi,id; int wi; }; int S,T; const int inf = 0x3f3f3f3f; std::vector<int> rk,cur; std::vector<std::vector<Flownode>> r; NetWorkFlow(int n,int s,int t) : r(n + 1),rk(n + 1,0),cur(n + 1),S(s),T(t){} int bfs() { std::fill(rk.begin(), rk.end(), 0); //memset(&rk[0],0,rk.size() * sizeof rk[0]); queue<int> q; q.push(S); rk[S] = 1; while(q.size()) { int x = q.front();q.pop(); for(auto tmp:r[x]) { if(!rk[tmp.vi] && tmp.wi) { rk[tmp.vi] = rk[x] + 1; q.push(tmp.vi); } } } return rk[T]; } int dfs(int x,int fl) { if(x == T) return fl; int res = fl; for(int &i = cur[x];i < r[x].size();i ++) { Flownode tmp = r[x][i]; if(rk[tmp.vi] == rk[x] + 1 && tmp.wi) { int flow = dfs(tmp.vi,min(tmp.wi,res)); r[x][i].wi -= flow; r[tmp.vi][r[x][i].id].wi += flow; res -= flow; if(res <= 0) break; } } if(fl == res) rk[x] = 0; return fl - res; } void addEdge(int u,int v,int val) { r[u].push_back({v,(int)r[v].size(),val}); r[v].push_back({u,(int)r[u].size() - 1,0}); } int Mxflow() { int ans = 0; while(bfs()) { for(auto &v:cur) v = 0; ans += dfs(S,inf); } return ans; } };
标签:tmp,int,vi,wi,算法,res,DINIC,模板,rk From: https://www.cnblogs.com/chayi/p/17585578.html