差别

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

--- 2020-2021:teams:legal_string:lgwza:类_dinic_算法 [2020/08/14 09:10]
lgwza [习题]
+++ 2020-2021:teams:legal_string:lgwza:类_dinic_算法 [2020/08/20 15:50] (当前版本)
lgwza
@@ 行 13: / 行 13: @@
 <hidden>
 <code cpp>
-#include <algorithm>
+#include<bits/stdc++.h>
-#include <cstdio>
+using namespace std;
-#include <cstring>
+const int N=5e3+5,M=1e5+5,INF=0x3f3f3f3f;
-#include <queue>
+int head[N],cur[N],to[M],nxt[M],dis[N],val[M],tot=1,cost[M];
-const int N = 5e3 + 5, M = 1e5 + 5;
-const int INF = 0x3f3f3f3f;
-int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
 bool vis[N];
+bool adj[N][N];
-void add(int u, int v, int w, int c) {
+void add(int u,int v,int c,int w){
-  ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
+	nxt[++tot]=head[u];
+	head[u]=tot;
+	to[tot]=v;
+	val[tot]=c;
+	cost[tot]=w;
 }
-void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
+void addedge(int u,int v,int c,int w){
-bool spfa(int s, int t) {
+	add(u,v,c,w);
-  memset(dis, 0x3f, sizeof(dis));
+	add(v,u,0,-w);
-  memcpy(cur, lnk, sizeof(lnk));
-  std::queue<int> q;
-  q.push(s), dis[s] = 0, vis[s] = 1;
-  while (!q.empty()) {
-    int u = q.front();
-    q.pop(), vis[u] = 0;
-    for (int i = lnk[u]; i; i = nxt[i]) {
-      int v = ter[i];
-      if (cap[i] && dis[v] > dis[u] + cost[i]) {
-        dis[v] = dis[u] + cost[i];
-        if (!vis[v]) q.push(v), vis[v] = 1;
-      }
-    }
-  }
-  return dis[t] != INF;
 }
-int dfs(int u, int t, int flow) {
+bool spfa(int s,int t){
-  if (u == t) return flow;
+	memset(dis,0x3f,sizeof(dis));
-  vis[u] = 1;
+	queue<int>que;
-  int ans = 0;
+	que.push(s);
-  for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
+	dis[s]=0;
-    int v = ter[i];
+	vis[s]=1;
-    if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
+	cur[s]=head[s];
-      int x = dfs(v, t, std::min(cap[i], flow - ans));
+	while(!que.empty()){
-      if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
+		int u=que.front();
-    }
+		que.pop();
-  }
+		vis[u]=0;
-  vis[u] = 0;
+		for(int i=head[u];i;i=nxt[i]){
-  return ans;
+			int v=to[i];
+			if(val[i]&&dis[v]>dis[u]+cost[i]){
+				dis[v]=dis[u]+cost[i];
+				cur[v]=head[v];
+				if(!vis[v])
+					que.push(v),vis[v]=1;
+			}
+		}
+	}
+	return dis[t]!=INF;
 }
-int mcmf(int s, int t) {
+int Cost;
-  int ans = 0;
+int dfs(int u,int ret,int s,int t){
-  while (spfa(s, t)) {
+	if(u==t||ret==0) return ret;
-    int x;
+	int Flow=0;
-    while ((x = dfs(s, t, INF))) ans += x;
+	vis[u]=1;
-  }
+	for(int i=cur[u];i&&ret;i=nxt[i]){
-  return ans;
+		int v=to[i];
+		cur[u]=i;
+		if(!vis[v]&&val[i]>0&&dis[v]==dis[u]+cost[i]){
+			int f=dfs(v,min(ret,val[i]),s,t);
+			if(f==0) vis[v]=0;
+			Cost+=f*cost[i];
+			val[i]-=f;
+			val[i^1]+=f;
+			Flow+=f;
+			ret-=f;
+		}
+	}
+	vis[u]=0;
+	return Flow;
 }
-int main() {
+int mcmf(int s,int t){
-  int s, t;
+	int Flow=0;
-  scanf("%d%d%d%d", &n, &m, &s, &t);
+	while(spfa(s,t)){
-  while (m--) {
+		Flow+=dfs(s,INF,s,t);
-    int u, v, w, c;
+	}
-    scanf("%d%d%d%d", &u, &v, &w, &c);
+	return Flow;
-    addedge(u, v, w, c);
+}
-  }
+int main(){
-  int ans = mcmf(s, t);
+//	freopen("P3381_8.in","r",stdin);
-  printf("%d %d\n", ans, ret);
+	int n,m,s,t;
-  return 0;
+	scanf("%d %d %d %d",&n,&m,&s,&t);
+	for(int i=1;i<=m;i++){
+		int u,v,c,w;
+		scanf("%d %d %d %d",&u,&v,&c,&w);
+		if(!adj[u][v])
+			addedge(u,v,c,w);
+		adj[u][v]=1;
+	}
+	printf("%d",mcmf(s,t));
+	printf(" %d",Cost);
+	return 0;
 }
 </code>
@@ 行 83: / 行 100: @@
 ===== 习题 =====
 [[https://www.luogu.com.cn/problem/P3381|「Luogu 3381」【模板】最小费用最大流]]
 [[https://www.luogu.com.cn/problem/P4452|「Luogu 4452」航班安排]]
 [[https://www.luogu.com.cn/problem/P2153|「SDOI 2009」晨跑]]
 [[https://www.luogu.com.cn/problem/P2053|「SCOI 2007」修车]]
 [[https://www.luogu.com.cn/problem/P2517|「HAOI 2010」订货]]
 [[https://loj.ac/problem/2674|「NOI 2012」美食节]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具