ISAP求调

P3376 【模板】网络最大流

Echoternity @ 2022-07-07 21:11:36

WA了3个点,各位巨佬拜托了qwq

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=201;
const int MAXM=5001;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,S,T;
struct Graph
{
    int next,to;
    ll val;
    Graph(int n=0,int t=0,ll v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,ll w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int Dep[MAXN],Num[MAXN];
inline void Bfs()
{
    memset(Dep,-1,sizeof(Dep));
    memset(Num,0,sizeof(Num));
    Dep[T]=0,Num[0]=1;
    queue<int>Q;
    Q.push(T);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u];e;e=Edge[e].next)
        {
            int v=Edge[e].to;
            if(Dep[v]!=-1) continue;
            Q.push(v);
            Dep[v]=Dep[u]+1;
            ++Num[Dep[v]];
        }
    }
    return ;
}
ll MaxFlow;
ll Dfs(int u,ll inf)
{
    if(u==T)
    {
        MaxFlow+=inf;
        return inf;
    }
    ll flow=0;
    for(int e=Head[u];e;e=Edge[e].next)
    {
        Cur[u]=e;
        int v=Edge[e].to;
        if(Edge[e].val&&Dep[v]+1==Dep[u])
        {
            ll k=Dfs(v,min(Edge[e].val,inf-flow));
            if(k)
            {
                Edge[e].val-=k;
                Edge[e^1].val+=k;
                flow+=k;
            }
            if(flow==inf) return flow;
        }
    }
    --Num[Dep[u]];
    if(Num[Dep[u]]==0) Dep[S]=N+1;
    ++Dep[u];
    ++Num[Dep[u]];
    return flow;
}
inline int ISAP()
{
    MaxFlow=0;
    Bfs();
    while(Dep[S]<N)
    {
        memcpy(Cur,Head,sizeof(Head));
        Dfs(S,INF);
    }
    return MaxFlow;
}
int main()
{
    // freopen("isap.in","r",stdin);
    // freopen("isap.out","w",stdout);
    read(N,M,S,T);
    for(int i=1,u,v;i<=M;++i)
    {
        ll w;
        read(u,v,w);
        addEdge(u,v,w);
    }
    printf("%lld",ISAP());
    return 0;
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
*/

by Echoternity @ 2022-07-07 21:47:38

\text{Fixed}

又双叒叕把 long long 打成 int


|