10pt MLE求助

P3376 【模板】网络最大流

Echoternity @ 2022-02-26 20:31:26

求助各路巨佬

#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 underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e4+1;
const int MAXM=1e4+1;
const int INF=0x7f7f7f7f;
template<class T>
inline void underRead(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;
}
int n,m,s,t,u,v,r;
struct edge
{
    int next,to,val;
    edge(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM];
int First[MAXN],Total,f[MAXN],t0[MAXN];
struct Que
{
    int u,r;
    Que(int u=0,int r=0):u(u),r(r){}
};
inline void underAdd(int u,int v,int r)
{
    Edge[++Total]=(edge){First[u],v,r},First[u]=Total;
}
inline bool underBfs()
{
    queue<int>Q;
    Q.push(s);
    memset(f,0,sizeof(f));
    f[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=First[u];e;e=Edge[e].next)
            if(!f[Edge[e].to]&&Edge[e].val)
            {
                f[Edge[e].to]=f[u]+1;
                Q.push(Edge[e].to);
            }
    }
    return f[t]!=0;
}
inline int underDfs(int x,int r)
{
    if(x==t) return r;
    int S=0;
    for(int e=t0[x];e;e=Edge[e].next)
    {
        t0[x]=e;
        if(f[Edge[e].to]=f[x]+1&&Edge[e].val)
        {
            int k=underDfs(Edge[e].to,underMin(r,Edge[e].val));
            if(k)
            {
                Edge[e].val-=k;
                Edge[e^1].val+=k;
                r-=k,S+=k;
            }
            else f[Edge[e].to]=0;
            if(!r) return S;
        }
    }
    return S;
}
int main()
{
    // freopen("maxinum-flow.in","r",stdin);
    // freopen("maxinum-flow.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&r);
        underAdd(u,v,r),underAdd(v,u,0);
    }
    int r=0;
    while(underBfs())
    {
        for(int i=1;i<=n;++i) t0[i]=First[i];
        r+=underDfs(s,INF);
    }
    printf("%d",r);
    return 0;
}
/*

*/

by OI_AKed_me @ 2022-02-26 20:37:09

inline int underDfs(int x,int r)

不能加inline


by Echoternity @ 2022-02-26 20:39:16

@shenyuchuan 加不加 inline 都是一样的吧,函数加了 inline 不是应该更快才对吗(猜测)


by OI_AKed_me @ 2022-02-26 20:40:16

你后面有递归调用


by OI_AKed_me @ 2022-02-26 20:40:49

递归调用应该不能用inline


by Echoternity @ 2022-02-26 20:43:01

@shenyuchuan 虽然明白了,但是去了 inline 依然 MLE


by OI_AKed_me @ 2022-02-26 20:44:28

那可能是你宽搜搜爆了


by Echoternity @ 2022-02-26 20:47:37

@shenyuchuan 感谢,调出来了

if(f[Edge[e].to]=f[x]+1&&Edge[e].val)

打错了


|