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
不懂