//这个是邻接矩阵的
#include<iostream> #include<queue> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std; const int maxn=500; const int inf=0x3f3f3f; int N; int depth[maxn]; int a[maxn][maxn]; bool bfs(int s,int e)//广搜求深度 { queue<int>q; memset(depth,-1,sizeof(depth));//初始-1 depth[s]=0; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(int i=1;i<=N;i++) { if(depth[i]==-1&&a[now][i])//两点有路，并且未搜过 { depth[i]=depth[now]+1; q.push(i); } } } return depth[e]>0; } int dfs(int now,int e,int nowflow) { if(now==N) return nowflow;//如果搜到最后 int findflow=0; for(int i=1;i<=N;i++) { if(a[now][i]&&depth[i]==depth[now]+1)//有路，并且为下一节点 { findflow=dfs(i,e,min(nowflow,a[now][i]));//继续dfs if(findflow) { a[now][i]-=findflow; a[i][now]+=findflow; return findflow; } } } if(!findflow) depth[now]=-2;//炸点优化 return false; } int dinic(int s,int e) { int maxflow=0; while(bfs(s,e)) maxflow+=dfs(s,e,1<<20); return maxflow; }
链式前向星
没听说过的同学 戳这里
#include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f; const int maxn = 1e5+5; struct node{ int v,w,next; node(int v1=0,int w1=0,int next1=0):v(v1),w(w1),next(next1){} }; node e[maxn<<1]; int head[maxn]; int tot; int N,E;//顶点数和边数 int dep[maxn];//求深度 int cur[maxn]//当前弧优化 void init() { tot=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w) { e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot++; //反向边 e[tot].v=u; e[tot].w=0; e[tot].next=head[v]; head[v]=tot++; } //bfs分层图 bool bfs(int ss,int ee) { memset(dep,-1,sizeof(dep)); queue<int>q; dep[ss]=0; q.push(ss); while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=e[i].next) { if(dep[e[i].v]==-1 && e[i].w>0) { dep[e[i].v]=dep[now]+1; q.push(e[i].v); } } } return dep[ee]!=-1; } //dfs搜索增广路径，now搜索顶点 ee终点 nowflow当前最大流 int dfs(int now,int ee,int nowflow) { // 搜索到终点或者 最大流为0 if(now==ee||nowflow==0) return nowflow; //useflow 可用流量 达到nowflow时不再增加 //maxflow 递归深搜时的最大流 int useflow=0,maxflow; //&i=cur[now] 为cur[now]起了个别名，为当前弧优化，每次更新cur[now]; for(int &i=cur[now]; i != -1 ; i = e[i].next) { if(e[i].w > 0 && dep[e[i].v] == dep[now] + 1) { maxflow = dfs(e[i].v, ee, min(nowflow-useflow, e[i].w)); if(maxflow>0) { e[i].w-=maxflow; e[i^1].w+=maxflow; useflow+=maxflow; if(uswflow == nowflow) return nowflow; } } } if(!useflow) dep[now]=-2; return useflow; } int dinic(int ss,int ee) { int ans=0; while(bfs(ss,ee)) { for(int i=1;i<=N;i++) cur[i]=head[i]; ans+=dfs(ss,ee,inf); } return ans; }