EK蜜汁64

Coros_Trusds @ 2021-03-29 13:53:18

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const unsigned long INF=1e9+5;

const int MA=1000005;

struct Edge
{
    int v;

    int xedge;
};

Edge dis[MA];

struct Node
{
    int v;

    int val;

    int nxt;
};

Node node[MA];

bool inque[MA];

int n,m,s,t;

int top=1;

int head[MA];

inline void add(int u,int v,int w)
{
    top++;

    node[top].val=w;

    node[top].v=v;

    node[top].nxt=head[u];

    head[u]=top;
}

inline bool bfs()
{
    queue<int>q;

    memset(inque,0,sizeof(inque));

    memset(dis,-1,sizeof(dis));

    inque[s]=true;

    q.push(s);

    while(!q.empty())
    {
        int f=q.front();

        q.pop();

        for(register int i=head[f];i;i=node[i].nxt)
        {
            int d=node[i].v;

            if(inque[d]==false && node[i].val>0)
            {
                dis[d].v=f;

                dis[d].xedge=i;

                if(d==t)
                {
                    return true;
                }

                inque[d]=true;

                q.push(d);
            }
        }
    }

    return false;
}

inline int Edmonds_Karp()
{
    int ans=0;

    while(bfs()==true)
    {
        int Min=INF;

        for(register int i=t;i!=s;i=dis[i].v)
        {
            Min=min(Min,node[dis[i].xedge].val);
        }

        for(register int i=t;i!=s;i=dis[i].v)
        {
            node[dis[i].xedge].val-=Min;

            node[dis[i].xedge^1].val+=Min;
        }

        ans+=Min;
    }

    return ans;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(register int i=1;i<=m;i++)
    {
        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,0);
    } 

    printf("%d\n",Edmonds_Karp());

    return 0;
}

by _LPF_ @ 2021-03-29 14:24:50

请注意边权 w 的范围。

应该是 \rm INF 设小了，然后统计答案时要开 long long

by Coros_Trusds @ 2021-03-29 22:27:54

@LPF

92pts

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef long long ll;

const int INF=(1<<30);

const int MA=1000005;

struct Edge
{
    int v;

    int xedge;
};

Edge dis[MA];

struct Node
{
    int v;

    ll val;

    int nxt;
};

Node node[MA];

bool inque[MA];

int n,m,s,t;

int top=1;

int head[MA];

inline void add(int u,int v,ll w)
{
    top++;

    node[top].val=w;

    node[top].v=v;

    node[top].nxt=head[u];

    head[u]=top;
}

inline bool bfs()
{
    queue<int>q;

    memset(inque,0,sizeof(inque));

    memset(dis,-1,sizeof(dis));

    inque[s]=true;

    q.push(s);

    while(!q.empty())
    {
        int f=q.front();

        q.pop();

        for(register int i=head[f];i;i=node[i].nxt)
        {
            int d=node[i].v;

            if(inque[d]==false && node[i].val>0)
            {
                dis[d].v=f;

                dis[d].xedge=i;

                if(d==t)
                {
                    return true;
                }

                inque[d]=true;

                q.push(d);
            }
        }
    }

    return false;
}

inline ll Edmonds_Karp()
{
    ll ans=0;

    while(bfs()==true)
    {
        ll  Min=INF;

        for(register int i=t;i!=s;i=dis[i].v)
        {
            Min=min(Min,node[dis[i].xedge].val);
        }

        for(register int i=t;i!=s;i=dis[i].v)
        {
            node[dis[i].xedge].val-=Min;

            node[dis[i].xedge^1].val+=Min;
        }

        ans+=Min;
    }

    return ans;
}

signed main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(register int i=1;i<=m;i++)
    {
        int u,v;

        ll w;

        scanf("%d%d%lld",&u,&v,&w);

        add(u,v,w);

        add(v,u,0);
    } 

    printf("%lld\n",Edmonds_Karp());

    return 0;
}

by _LPF_ @ 2021-03-30 00:06:55