AC_love @ 2023-09-26 20:15:32
vector 党震怒
所以如果写一篇对最大流算法介绍和其他题解都一样的题解，然后详细介绍如何用 vector 实现最大流算法的话，可以联系管理员添加题解吗？
by userLCX @ 2023-09-26 20:18:31
vector能写当前弧优化么（）
by Kazdale @ 2023-09-26 20:20:26
vector能写当前弧优化么（）
by _zzzzzzy_ @ 2023-09-26 20:20:44
vector能写当前弧优化么（）
by Sparkle_Infinity @ 2023-09-26 20:23:50
能写啊
by cnyzz @ 2023-09-26 20:24:00
vector 还真可以当前弧
by what_can_I_do @ 2023-09-26 20:24:40
我就用vector
by Perfound @ 2023-09-26 20:24:44
@userLCX 为什么不能当前弧优化啊，不是只是不好取反向边吧
by Aleph_Drawer @ 2023-09-26 20:24:48
我错了。呜呜呜。
但是应该是不可以的吧。
by cnyzz @ 2023-09-26 20:26:57
贴一份 cmd 写的 vector 网络流带当前弧优化
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define INF 1000000000
#define Maxn 10500
using namespace std;
struct Line{int t,cap,b;};
vector<Line> g[Maxn];
void adl(int f,int t,int cap){
g[f].pb((Line){t,cap,g[t].size()});
g[t].pb((Line){f,0,g[f].size()-1});
}
int n,m,S,T,dis[Maxn],cur[Maxn];
bool bfs()
{
static queue<int> q;
for (int i=1;i<=n;i++){cur[i]=dis[i]=0;}
q.push(S);dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0,v;i<g[u].size();i++)
if (g[u][i].cap&&!dis[v=g[u][i].t]){
dis[v]=dis[u]+1;
if (v==T){
while(!q.empty())q.pop();
return 1;
}
q.push(v);
}
}return dis[T];
}
int dfs(int u,int flow)
{
if (u==T)return flow;
int sum=0;
for (int &i=cur[u],v;i<g[u].size();i++)
if (dis[v=g[u][i].t]==dis[u]+1&&g[u][i].cap){
int sav=dfs(v,min(flow,g[u][i].cap));
if (sav){
g[u][i].cap-=sav;
g[v][g[u][i].b].cap+=sav;
sum+=sav;flow-=sav;
if (!flow)return sum;
}else dis[v]=-1;
}
return sum;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for (int i=1,f,t,cap;i<=m;i++){
scanf("%d%d%d",&f,&t,&cap);
adl(f,t,cap);
}int ans=0;
while(bfs())ans+=dfs(S,INF);
printf("%d",ans);
return 0;
}by AC_love @ 2023-09-26 20:27:49
@Perfound 反向边应该挺好取的，就这样就行
for(int i = 1; i <= m; i = i + 1)
{
int st, ed, len;
cin >> st >> ed >> len;
int sti = e[st].size();
int edi = e[ed].size();
e[st].push_back((edge){ed, len, edi});
e[ed].push_back((edge){st, 0, sti});
// 残留网络中正向边流量为 len，反向边流量为 0
}