差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:dinic_算法 [2020/08/13 16:24]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:dinic_算法 [2020/08/16 15:26] (当前版本)
lgwza [Dinic 算法]
@@ 行 1: / 行 1: @@
 ====== Dinic 算法 ======
-**Dinic 算法** 可用于求解网络最大流问题
+**Dinic 算法** 可用于求解网络最大流问题。
 **Dinic 算法** 的过程是这样的：每次增广前，我们先用 BFS 来将图分层。设源点的层数为 $0$，那么一个点的层数便是它离源点的最近距离。
@@ 行 29: / 行 29: @@
 参考代码：
+<hidden>
 <code cpp>
 #include<bits/stdc++.h>
 using namespace std;
-#define maxn 205
-#define INF 0x3f3f3f3f
 typedef long long ll;
+const int N=205,M=1e4+5;
-struct Edge {
+const ll INF=0x3f3f3f3f;
-  ll from, to, cap, flow;
+int tot=1,head[N],cur[N],to[M],nxt[M],level[N];
-  Edge(ll u, ll v, ll c, ll f) : from(u), to(v), cap(c), flow(f) {}
+ll val[M];//剩余容量
-};
+bool vis[N];
+void add(int u,int v,ll c){
-struct Dinic {
+	nxt[++tot]=head[u];
-  ll n, m, s, t;
+	head[u]=tot;
-  vector<Edge> edges;
+	to[tot]=v;
-  vector<ll> G[maxn];
+	val[tot]=c;
-  ll d[maxn], cur[maxn];
+}
-  bool vis[maxn];
+void addedge(int u,int v,ll c){
+	add(u,v,c);
-  void init(ll n) {
+	add(v,u,0);
-    for (ll i = 1; i <= n; i++) G[i].clear();
+}
-    edges.clear();
+bool BFS(int s,int t){
-    memset(d,0,sizeof(d));
+	memset(vis,0,sizeof(vis));
-    memset(cur,0,sizeof(cur));
+	queue<int>que;
-    memset(vis,0,sizeof(vis));
+	que.push(s);
-  }
+	level[s]=0;
+	vis[s]=1;
-  void AddEdge(ll from, ll to, ll cap) {
+	cur[s]=head[s];
-    edges.push_back(Edge(from, to, cap, 0));
+	while(!que.empty()){
-    edges.push_back(Edge(to, from, 0, 0));
+		int u=que.front();
-    m = edges.size();
+		que.pop();
-    G[from].push_back(m - 2);
+		for(int i=head[u];i;i=nxt[i]){
-    G[to].push_back(m - 1);
+			int v=to[i];
-  }
+			if(!vis[v]&&val[i]>0){
+				vis[v]=1;
-  bool BFS() {
+				level[v]=level[u]+1;
-    memset(vis, 0, sizeof(vis));
+				cur[v]=head[v];
-    queue<ll> Q;
+				que.push(v);
-    Q.push(s);
+				if(v==t) return true;
-    d[s] = 0;
+			}
-    vis[s] = 1;
+		}
-    while (!Q.empty()) {
+	}
-      ll x = Q.front();
+	return vis[t];
-      Q.pop();
+}
-      for (ll i = 0; i < G[x].size(); i++) {
+ll DFS(int u,ll ret,int s,int t){
-        Edge& e = edges[G[x][i]];
+	if(u==t||ret==0) return ret;//ret 表示 S 到这里最多能流入的流量
-        if (!vis[e.to] && e.cap > e.flow) {
+	ll Flow=0,f;//Flow 表示经过该点的所有流量和（相当于流出的总量）；f 表示当前最小的剩余容量
-          vis[e.to] = 1;
+	for(int i=cur[u];i&&ret;i=nxt[i]){
-          d[e.to] = d[x] + 1;
+		cur[u]=i;//当前弧优化
-          Q.push(e.to);
+		int v=to[i];
-        }
+		if(level[u]+1==level[v]&&val[i]>0){
-      }
+			f=DFS(v,min(ret,val[i]),s,t);
-    }
+			if(f==0) vis[v]=0;
-    return vis[t];
+			val[i]-=f;
-  }
+			val[i^1]+=f;
+			Flow+=f;
-  ll DFS(ll x, ll a) {
+			ret-=f;
-    if (x == t || a == 0) return a;
+		}
-    ll flow = 0, f;
+	}
-    for (ll& i = cur[x]; i < G[x].size(); i++) {
+	return Flow;//返回实际使用的流量
-      Edge& e = edges[G[x][i]];
+}
-      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
+ll Dinic(int s,int t){
-        e.flow += f;
+	ll Flow=0;
-        edges[G[x][i] ^ 1].flow -= f;
+	while(BFS(s,t)){
-        flow += f;
+		Flow+=DFS(s,INF,s,t);
-        a -= f;
+	}
-        if (a == 0) break;
+	return Flow;
-      }
+}
-    }
-    return flow;
-  }
-  ll Maxflow(ll s, ll t) {
-    this->s = s;
-    this->t = t;
-    ll flow = 0;
-    while (BFS()) {
-      memset(cur, 0, sizeof(cur));
-      flow += DFS(s, INF);
-    }
-    return flow;
-  }
-}D;
 int main(){
-    ll n,m,s,t;
+	int n,m,s,t;
-    scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
+	scanf("%d %d %d %d",&n,&m,&s,&t);
-    D.init(n);
+	for(int i=1;i<=m;i++){
-    for(ll i=1;i<=m;i++){
+		int u,v;
-        ll u,v,w;
+		ll c;
-        scanf("%lld %lld %lld",&u,&v,&w);
+		scanf("%d %d %lld",&u,&v,&c);
-        D.AddEdge(u,v,w);
+		addedge(u,v,c);
-    }
+	}
-    printf("%lld",D.Maxflow(s,t));
+	printf("%lld",Dinic(s,t));
-    return 0;
+	return 0;
 }
 </code>
+</hidden>
 ===== 参考链接 =====
 [[https://oi-wiki.org/graph/flow/max-flow/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具