Dinic

港控/mmm° 2021-11-22 08:50 221阅读 0赞

#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> #include<ctime> #include<map> #include<queue> #include<cstdlib> #include<string> #include<climits> #include<set> #include<vector> using namespace std; const int maxN=1000005,maxM=1000005,oo=10000000000000000ll; int n,m,s,t,cnt,Head[maxN],Next[maxM],W[maxM],V[maxM],Depth[maxN],cur[maxN]; void _Add(int u,int v,int w){ cnt++; Next[cnt]=Head[u]; Head[u]=cnt; V[cnt]=v; W[cnt]=w; } void Add_Edge(int u,int v,int w){ _Add(u,v,w); _Add(v,u,0); } int dfs(int u,int flow){ if(u==t){ return flow; } for(int& i=cur[u];i!=-1;i=Next[i]){ if((Depth[V[i]]==Depth[u]+1)&&(W[i]!=0)){ int di=dfs(V[i],min(flow,W[i])); if(di>0){ W[i]-=di; W[i^1]+=di; return di; } } } return 0; } int bfs(){ queue<int> Q; while(!Q.empty()){ Q.pop(); } memset(Depth,0,sizeof(Depth)); Depth[s]=1; Q.push(s); do{ int u=Q.front(); Q.pop(); for(int i=Head[u];i!=-1;i=Next[i]){ if((Depth[V[i]]==0)&&(W[i]>0)){ Depth[V[i]]=Depth[u]+1; Q.push(V[i]); } } } while(!Q.empty()); if(Depth[t]>0){ return 1; } return 0; } int Dinic(){ int Ans=0; while (bfs()){ for(int i=1;i<=n;i++){ cur[i]=Head[i]; } while(int d=dfs(s,oo)){ Ans+=d; } } return Ans; } int main(){ int u,v,w; cnt=-1; memset(Head,-1,sizeof(Head)); memset(Next,-1,sizeof(Next)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); Add_Edge(u,v,w); } printf("%d\n",Dinic()); return 0; }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11194257.html

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关 dinic算法 c 语言,网络流入门—用于最大流的Dinic算法

“网络流博大精深”—sideman语 ![L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9kaX

r囧r小猫/ 2022年10月15日 05:54/ 0 赞/ 199 阅读

相关 POJ 3469-Dual Core CPU（Dinic 最大流/最小割算法）

Dual Core CPU <table> <tbody> <tr> <td><strong>Time Limit:</strong> 15000

Myth丶恋晨/ 2022年09月25日 06:26/ 0 赞/ 182 阅读

相关【最大流-Dinic算法】B - Dining POJ - 3281

Think: 1知识点：【最大流-Dinic算法】+【建图】 2题意：输入N, F, D, 代表N头奶牛，F个食物，D个饮料，每头奶牛只吃喜欢的食物，只喝喜欢的饮料，询

偏执的太偏执、/ 2022年06月10日 08:41/ 0 赞/ 180 阅读

相关【最大流模板——Dinic算法】【有向图】

include <cstdio> include <cstring> include <algorithm> include <queue>

た入场券/ 2022年06月10日 07:46/ 0 赞/ 155 阅读

相关 POJ 1459 Power Network（最大流+dinic算法模板）

A power network consists of nodes (power stations, consumers and dispatchers) connected

水深无声/ 2022年06月09日 11:09/ 0 赞/ 152 阅读

相关最大流算法：Edmond-Karp算法——Ford-Fulkerson算法——Dinic算法

问题定义限制条件示例基本思想引入反向边 Edmond-Karp算法 Ford-Fulkerson算法使用DFS的For

骑猪看日落/ 2022年05月19日 12:27/ 0 赞/ 492 阅读

相关 (模板) Dinic 最大流

代码 / DINIC 模板 BEGIN / / 需要的头文件 include <string.h> include <queue> inc

谁借莪１个温暖的怀抱￠/ 2022年04月25日 02:34/ 0 赞/ 172 阅读

相关 Dinic

include<cstdio> include<algorithm> include<cmath> include<cstring> include<iostream>

港控/mmm°/ 2021年11月22日 08:50/ 0 赞/ 222 阅读

相关我学会了正确的dinic

以前写Isap的时候，总是被卡，然后学了一发Isap的当前弧优化，好像可以水过很多题但是一直没明白为啥Isap会走一个环？？？然后写dinic了，听说不容易被卡（来自

￡神魔★判官ぃ/ 2021年11月01日 13:46/ 0 赞/ 276 阅读

相关模板——网络流Dinic

感谢这位大佬的博客：[https://www.cnblogs.com/SYCstudio/p/7260613.html][https_www.cnblogs.com_SYCst

Bertha 。/ 2021年11月01日 13:24/ 0 赞/ 320 阅读