深夜交题，re爆零

bjckwrn @ 2020-09-30 01:00:40

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000;
const int M=25000;
const int MAX_V=25000;
const ll inf=0x3f3f3f3f;

struct edge{int to;ll cap;int rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,ll cap)
{
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
    return ;
}

void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int v=que.front(); que.pop();
        for(int i=0;i<G[v].size();i++)
        {
            edge &e=G[v][i];
            if(e.cap>(ll)0&&level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
    return ;
}

int dfs(int v,int t,ll f)
{
    if(v==t) return f;
    for(int &i=iter[v];i<G[v].size();i++)
    {
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to])
        {
            ll d=dfs(e.to,t,min(f,e.cap));
            if(d>0) 
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
}

ll max_flow(int s,int t)
{
    ll flow=0;
    for(;;)
    {
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        ll f;
        while((f=dfs(s,t,inf))>0) flow+=f; 
    }
}

int main()
{

    int x,y,i,j,n,m,S,T;
    ll z;
    scanf("%d %d %d %d",&n,&m,&S,&T);
    for(i=1;i<=n;i++) G[i].clear();
    for(i=1;i<=m;i++)
    {
    scanf("%d %d %lld",&x,&y,&z);
    add_edge(x,y,z);
    }
    ll ans=max_flow(S,T);
    printf("%lld\n",ans);

    return 0;
}

by hly1204 @ 2020-09-30 01:53:53

@bjckwrn 稍微修改了一下，现在能通过了，但是 (edge){} 这种形式尽量不要用，好像这个不是标准，然后里面有个收缩的强制类型转换，这里不太能设置成隐式的，所以显式转换一下，还有在 dfs 最后要返回一个值。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000;
const int M=25000;
const int MAX_V=25000;
const ll inf=0x3f3f3f3f;

struct edge{int to;ll cap;int rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,ll cap)
{
    G[from].push_back((edge){to,cap,int(G[to].size())});
    G[to].push_back((edge){from,0,int(G[from].size())-1});
    return ;
}

void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int v=que.front(); que.pop();
        for(int i=0;i<G[v].size();i++)
        {
            edge &e=G[v][i];
            if(e.cap>(ll)0&&level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
    return ;
}

int dfs(int v,int t,ll f)
{
    if(v==t) return f;
    for(int &i=iter[v];i<G[v].size();i++)
    {
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to])
        {
            ll d=dfs(e.to,t,min(f,e.cap));
            if(d>0) 
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

ll max_flow(int s,int t)
{
    ll flow=0;
    for(;;)
    {
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        ll f;
        while((f=dfs(s,t,inf))>0) flow+=f; 
    }
}

int main()
{

    int x,y,i,j,n,m,S,T;
    ll z;
    scanf("%d %d %d %d",&n,&m,&S,&T);
    for(i=1;i<=n;i++) G[i].clear();
    for(i=1;i<=m;i++)
    {
    scanf("%d %d %lld",&x,&y,&z);
    add_edge(x,y,z);
    }
    ll ans=max_flow(S,T);
    printf("%lld\n",ans);

    return 0;
}

by bjckwrn @ 2020-09-30 11:32:19

@hly1204 非常感谢深夜回复，改了dfs和强转果然a了，照着书都能抄错。