样例没过却AC,求dalao

P3376 【模板】网络最大流

zyywzw @ 2019-08-03 17:58:43

RT

#include<bits/stdc++.h>
#define REP(i,a,b) for(register int i(a);i<=b;i++)
using namespace std;
const int N=1e4+100;
const int M=1e5+100;
const int INF=2e8+10;
int n,m,s,t,x,y,z,maxflow;
int head[N],cur[N],tot=-1;
struct edge{int to,nxt,cap;}G[M<<1];
int dep[N],use[N];
template<class T>inline void read(T&x){
    T r=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}
    x=r*f;
}
inline void add(int x,int y,int z){G[++tot]=(edge){y,head[x],z};head[x]=tot;}
inline int BFS(){
    queue<int>q;
    memset(dep,-1,sizeof(dep));
    q.push(s);dep[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        for(register int i=head[u];i;i=G[i].nxt){
            int v=G[i].to;
            if(dep[v]==-1&&G[i].cap)
            {dep[v]=dep[u]+1;q.push(v);}
        }
    }
    return dep[t]!=-1;
}
inline int dfs(int u,int f){
    if(u==t)return f;
    int lft,used=0;
    for(register int i=cur[u];i;i=G[i].nxt){
        if(dep[G[i].to]==dep[u]+1&&G[i].cap){
            lft=f-used;lft=dfs(G[i].to,min(G[i].cap,lft));
            G[i].cap-=lft;if(G[i].cap)cur[u]=i;
            G[i^1].cap+=lft;used+=lft;
        }
    }
    if(!used)dep[u]=-1;
    return used;
} 
inline void Dinic(){
    while(BFS()){
        REP(i,1,n)cur[i]=head[i];
        maxflow+=dfs(s,INF);
    }
    cout<<maxflow;
}
int main(){
    read(n);read(m);read(s);read(t);
    REP(i,1,m){read(x);read(y);read(z);
    add(x,y,z);add(y,x,0);}
    Dinic();
}

by Vn_nV @ 2019-08-03 17:59:37

洛谷数据水


by 塔罗兰 @ 2019-08-03 18:20:56

我更好奇你样例都没过是怎么有勇气交上去的


|