警示后人

P3376 【模板】网络最大流

还有一个问题,在`zwk`中会出现,但是本题可过 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define r(x) (x^1) #define add(u,vf,c,d) ( sum+=2,E[sum].v=vf,E[sum].val=c,E[r(sum)].v=u,E[r(sum)].val=d,G[u].push_back(sum),G[vf].push_back(r(sum)) ) #define MAXX 100010 #define inf 0x3f3f3f3f int S,T,n,m,sum=0; struct node{ int v,val; }E[MAXX]; vector<int> G[MAXX]; int dep[MAXX],inque[MAXX],cur[MAXX]; bool bfs(){ for(int i=0;i<MAXX;i++) cur[i]=0,dep[i]=inf,inque[i]=0; dep[S]=0; queue<int> q; q.push(S); while(!q.empty()){ int x=q.front(); q.pop(); inque[x]=0; for(int i=0;i<G[x].size();i++){ int tx=G[x][i]; if(dep[E[tx].v]>dep[x]+1 && E[tx].val){ dep[E[tx].v]=dep[x]+1; if(!inque[E[tx].v]) q.push(E[tx].v),inque[E[tx].v]=1; } } } if(dep[T]!=inf) return true; return false; } int dfs(int x,int flow){ int rlow=0,used=0; if(x==T) return flow; for(int i=cur[x];i<G[x].size();i++){ cur[x]=i; int tx=G[x][i]; if(E[tx].val && dep[E[tx].v]==dep[x]+1){ if(rlow=dfs(E[tx].v,min(flow-used,E[tx].val))){ used+=rlow,E[tx].val-=rlow,E[r(tx)].val+=rlow; if(used==flow) break; } } } return used; } int dinic(){ int ans=0,cnt; while(bfs()) while(cnt=dfs(S,inf)) ans+=cnt; return ans; } inline ll read(); signed main (){ n=read(),m=read(),S=read(),T=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),val=read(); add(u,v,val,0); } cout<<dinic()<<endl; return 0; } inline ll read(){ ll k=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar();} while(ch>='0' && ch<='9') k=k*10+ch-'0',ch=getchar(); return k*f; } ``` 中`if(!inque[E[tx].v]) ` 写成`if(!inque[tx]) `
by orgn @ 2023-03-03 18:49:03


|