rerain @ 2023-02-25 09:19:59
修改前
int sap(int s,int t){
bfs(s,t);
int ret=0;
while(dis[s]<=n){
ret+=dfs(s,t,s,inf);
}
return ret;
}
改long long就过了
修改后
by orgn @ 2023-03-03 18:49:03
还有一个问题,在zwk
中会出现,但是本题可过
#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])