警示后人

P3376 【模板】网络最大流

rerain @ 2023-02-25 09:19:59

不开long long见祖宗

修改前

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])


|