关于 vector 存图
很多网上的资料（视频、题解）的最大流算法为了方便找反边，都使用了链式前向星。
但是！
vector 党表示不服！
于是在进行学习后，笔者归纳出了两种 vector 存图并快速找反边的方法。
存储反边编号
一般 vector 实现邻接表是形如这样的：（在最大流相关算法中）
struct edge
{
int v,w;
};
vector<edge> e[N];
inline void addedge(int u,int v,int w)
{
e[u].push_back({v,w});
e[v].push_back({u,0});
}
但是这种存储方法无法快速找到反边。
考虑在结构体 edge 中添加一个信息 x：
struct edge
{
int v,w,x;
};
表示反边为 e[v][x]。那么加边时也相应的需要修改：
inline void addedge(int u,int v,int w)
{
e[u].push_back({v,w,int(e[v].size())});
e[v].push_back({u,0,int(e[u].size()-1)});
}
这样就可以快速实现找反边操作了。（关于为什么是 int(e[v].size())、int(e[u].size()-1) 请自行思考。）
注意，EK 算法中 int pre[N] 数组则需要改成 pair<int,int> pre[N]，分别表示来自 first 号点和它的 second 号边。
这里放出 EK 板子和 Dinic 板子：
EK：
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
int v;
ll c;
int x;
};
vector<edge> e[N];
int n,m,s,t;
namespace EK
{
bitset<N> vis;
pii pre[N];
ll flow[N];
bool bfs()
{
queue<int> q;
vis.reset();
vis[s]=true;
q.push(s);
flow[s]=INF;
int u,l,v;
ll c;
while(!q.empty())
{
u=q.front();
q.pop();
l=e[u].size();
for(int i=0;i<l;i++)
{
v=e[u][i].v;
c=e[u][i].c;
if(!vis[v]&&c>0)
{
vis[v]=true;
flow[v]=min(flow[u],c);
pre[v]={u,i};
if(v==t)return true;
q.push(v);
}
}
}
return false;
}
ll EK()
{
ll r=0ll;
while(bfs())
{
r+=flow[t];
for(int i=t;i!=s;i=pre[i].first)
{
e[pre[i].first][pre[i].second].c-=flow[t];
e[i][e[pre[i].first][pre[i].second].x].c+=flow[t];
}
}
return r;
}
}//^ namespace EK
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
e[u].push_back({v,ll(w),int(e[v].size())});
e[v].push_back({u,0ll,int(e[u].size()-1)});
}
printf("%lld",EK::EK());
return 0;
}
Dinic：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
int v;
ll c;
int x;
};
vector<edge> e[N];
int n,m,s,t;
namespace Dinic
{
int dis[N],fir[N];
bool bfs()
{
fill(fir,fir+N,0);
fill(dis,dis+N,0);
dis[s]=1;
queue<int> q;
q.push(s);
int u,l,v;
while(!q.empty())
{
u=q.front();
q.pop();
l=e[u].size();
for(int i=0;i<l;i++)
{
v=e[u][i].v;
if(!dis[v]&&e[u][i].c>0ll)
{
dis[v]=dis[u]+1;
q.push(v);
if(v==t)return true;
}
}
}
return false;
}
ll dfs(int u=s,ll flow=INF)
{
if(u==t)return flow;
int l=e[u].size(),v;
ll res=0ll,now,c;
for(int i=fir[u];i<l;i++)
{
fir[u]=i;
v=e[u][i].v;
c=e[u][i].c;
if(dis[v]==dis[u]+1&&c>0ll)
{
now=dfs(v,min(flow,c));
if(now==0ll)dis[v]=0;
e[u][i].c-=now;
e[v][e[u][i].x].c+=now;
res+=now;
flow-=now;
if(flow==0ll)return res;
}
}
return res;
}
ll Dinic()
{
ll r=0ll;
while(bfs())r+=dfs();
return r;
}
}//^ namespace Dinic
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
e[u].push_back({v,ll(w),int(e[v].size())});
e[v].push_back({u,0ll,int(e[u].size()-1)});
}
printf("%lld",Dinic::Dinic());
return 0;
}
将边存入池子并保存编号
我们可以使用两个 vector 实现更方便的存边方式：
vector<edge> es;
vector<int> e[N];
其中 es 存了所有边，e[u] 中存 u 的所有出边在 es 中的编号。
于是，如果我们需要知道边 e[u][i] 的信息，只需要访问 es[e[u][i]]。
而 e[u][i] 的反边即为 e[u][i]^1，与传统链式前向星的访问反边方式类似。
存边时：
e[u].push_back(es.size());
es.push_back({v,ll(w)});
e[v].push_back(es.size());
es.push_back({u,0ll});
依然给出板子：
EK：
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
int v;
ll c;
};
vector<edge> es;
vector<int> e[N];
int n,m,s,t;
namespace EK
{
bitset<N> vis;
int pre[N];
ll flow[N];
bool bfs()
{
queue<int> q;
vis.reset();
vis[s]=true;
q.push(s);
flow[s]=INF;
int u,l,v;
ll c;
while(!q.empty())
{
u=q.front();
q.pop();
l=e[u].size();
for(int i=0;i<l;i++)
{
v=es[e[u][i]].v;
c=es[e[u][i]].c;
if(!vis[v]&&c>0)
{
vis[v]=true;
flow[v]=min(flow[u],c);
pre[v]=e[u][i];
if(v==t)return true;
q.push(v);
}
}
}
return false;
}
ll EK()
{
ll r=0ll;
while(bfs())
{
r+=flow[t];
for(int i=t;i!=s;i=es[pre[i]^1].v)
{
es[pre[i]].c-=flow[t];
es[pre[i]^1].c+=flow[t];
}
}
return r;
}
}//^ namespace EK
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
e[u].push_back(es.size());
es.push_back({v,ll(w)});
e[v].push_back(es.size());
es.push_back({u,0ll});
}
printf("%lld",EK::EK());
return 0;
}
Dinic：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
int v;
ll c;
};
vector<edge> es;
vector<int> e[N];
int n,m,s,t;
namespace Dinic
{
int dis[N],fir[N];
bool bfs()
{
fill(fir,fir+N,0);
fill(dis,dis+N,0);
dis[s]=1;
queue<int> q;
q.push(s);
int u,l,v;
while(!q.empty())
{
u=q.front();
q.pop();
l=e[u].size();
for(int i=0;i<l;i++)
{
v=es[e[u][i]].v;
if(!dis[v]&&es[e[u][i]].c>0ll)
{
dis[v]=dis[u]+1;
q.push(v);
if(v==t)return true;
}
}
}
return false;
}
ll dfs(int u=s,ll flow=INF)
{
if(u==t)return flow;
int l=e[u].size(),v;
ll res=0ll,now,c;
for(int i=fir[u];i<l;i++)
{
fir[u]=i;
v=es[e[u][i]].v;
c=es[e[u][i]].c;
if(dis[v]==dis[u]+1&&c>0ll)
{
now=dfs(v,min(flow,c));
if(now==0ll)dis[v]=0;
es[e[u][i]].c-=now;
es[e[u][i]^1].c+=now;
res+=now;
flow-=now;
if(flow==0ll)return res;
}
}
return res;
}
ll Dinic()
{
ll r=0ll;
while(bfs())r+=dfs();
return r;
}
}//^ namespace Dinic
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
e[u].push_back(es.size());
es.push_back({v,ll(w)});
e[v].push_back(es.size());
es.push_back({u,0ll});
}
printf("%lld",Dinic::Dinic());
return 0;
}
正文
咕……
标签：return,最大,int,ll,flow,网络,push,es From： https://www.cnblogs.com/chargedcreeper/p/max-flow.html