求助:关于当前弧优化

P3376 【模板】网络最大流

bulijoijiodibuliduo @ 2022-08-17 14:23:23

当前弧优化的时候如果用引用要900+ms

但是如果每次重新赋值就是60+ms

我的代码:

#include<bits/stdc++.h>
using namespace std;
#define fin(s) freopen(s,"r",stdin)
#define fout(s) freopen(s,"w",stdout)
#define fio(s) {fin(s".in");fout(s".out");}
#define rep(i,a,b) for(auto i=(a);i<=(b);i++)
#define per(i,a,b) for(auto i=(a);i>=(b);i--)
#define fi first
#define se second
#define ll long long
#define lll __int128
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vli vector<pli>
#define vil vector<pil>
#define vll vector<pll>
#define eb emplace_back
#define All(a) (a).begin(),(a).end()
#define Size(a) ((int)(a).size())
#define mem(a,b) memset(a,b,sizeof(a))
#define err qout<<"#"<<__LINE__<<": "
const ll mod=1e9+7;
mt19937 rnd(random_device{}());
#define local
#if defined(local)
#define qin cin
#define qout cout
#else
struct qistream{
  FILE *in;char buf[65536],*p1=buf,*p2=buf;qistream(FILE *in):in(in){}
  char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,in),p1==p2)?EOF:*p1++;}
  template<typename T>void read(T &x){
    x=0;T f=1;char ch=gc();
    for(;!isdigit(ch);)f=ch=='-'?-1:1,ch=gc();
    for(;isdigit(ch);)x=(x<<1)+(x<<3)+ch-48,ch=gc();
    x*=f;
  }
  template<typename T>qistream& operator>>(T& x){read(x);return *this;}
  qistream& operator>>(char& x){x=' ';for(;x<=' ';)x=gc();return *this;}
  qistream& operator>>(char *x){
    int i=0;char c=' ';
    for(;c<=' ';)c=gc();for(;c>' ';)x[i++]=c,c=gc();
    x[i]=0;return *this;
  }
}qin(stdin);
struct qostream{
  FILE *out;char buf[65536],*p=buf;qostream(FILE *out):out(out){}
  void pc(char x){p-buf<65536?*p++=x:(fwrite(buf,p-buf,1,out),p=buf,*p++=x);}
  void flush(){fwrite(buf,p-buf,1,out);}
  ~qostream(){flush();}
  template<typename T>void write(T x){
    if(x<0){pc('-');if(x<-9)write(-(x/10));pc(48-x%10);}
    else{if(x>9)write(x/10);pc(48+x%10);}
  }
  template<typename T>qostream& operator<<(T x){write(x);return *this;}
  qostream& operator<<(const char x){pc(x);return *this;}
  qostream& operator<<(const char *x){for(int i=0;x[i];++i)pc(x[i]);return *this;}
}qout(stdout);
#endif
const int inf=2e9,N=1e5,M=1e5;
int head[N],nxt[M],to[M],cap[M],dis[N],cur[N],n,m,s,t,tot=1;
void add(int x,int y,int c){tot++;to[tot]=y;cap[tot]=c;nxt[tot]=head[x];head[x]=tot;}
void addedge(int x,int y,int c){add(x,y,c),add(y,x,0);}
bool bfs(){
  rep(i,1,n)dis[i]=0,cur[i]=head[i];
  queue<int>q;dis[s]=1;q.emplace(s);
  while(!q.empty()){
    int x=q.front();q.pop();
    for(int i=head[x];i;i=nxt[i]){
      int y=to[i];
      if(dis[y]||!cap[i])continue;
      dis[y]=dis[x]+1;q.push(y);
    }
  }
  return dis[t];
}
int dfs(int x,int flow){
  if(x==t||!flow)return flow;
  int res=flow;
  for(int i=cur[x];i&&res;i=nxt[i]){
    cur[x]=i;//这里是当前弧优化
    int y=to[i];
    if(!cap[i]||dis[y]!=dis[x]+1)continue;
    int k=dfs(y,min(res,cap[i]));
    if(k)cap[i]-=k,cap[i^1]+=k,res-=k;
    else dis[y]=0;
  }
  return flow-res;
}
ll dinic(){ll ans=0;while(bfs())ans+=dfs(s,inf);return ans;}
int main(){
  qin>>n>>m>>s>>t;
  rep(i,1,m){
    int x,y,c;
    qin>>x>>y>>c;
    addedge(x,y,c);
  }
  qout<<dinic();
}

by bulijoijoidibuliduo @ 2022-08-17 14:43:54

Cu Ball qwq


by I_am_Accepted @ 2022-08-17 17:50:40

不懂


by Z_301 @ 2022-10-07 19:28:52

Cu ball


by Nuisdete @ 2022-11-26 10:12:22

不懂


|