求助网络毒瘤

P3376 【模板】网络最大流

Lucifero @ 2021-07-20 11:25:09

#include <bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
using namespace std;
class Edge
{
public:
    int u,v,w,next;
}e[100001];
queue<int> r;
int elast[201],cur[201],level[201],cnt[201],n,s,t,link(1),ans;
void add(int u,int v,int w)
{
    e[++link]=(Edge){u,v,w,elast[u]};
    elast[u]=link;
}
void bfs(int u)
{
    memset(level,inf,sizeof(level));
    cnt[level[u]=0]=1;
    r.push(u);
    int v,i;
    while(!r.empty())
    {
        u=r.front(),r.pop();
        for(i=elast[u];i!=0;i=e[i].next)
        {
            v=e[i].v;
            if (level[v]>=inf)
            {
                cnt[level[v]=level[u]+1]++;
                r.push(v);
            }
        }
    }
}
int augment(int u,int flow)
{
    int v,k(0),temp,i;
    if (u==t) return flow;
    for(i=cur[u];i!=0;i=e[i].next)
    {
        cur[u]=i;
        v=e[i].v;
        if (e[i].w>0 && level[u]==level[v]+1)
        {
            temp=augment(v,min(flow-k,e[i].w));
            e[i].w-=temp,e[i^1].w+=temp;
            k+=temp;
            if (k==flow || level[s]>t)
                return k;
        }
    }
    if (level[s]>t) return k;
    cnt[level[u]]--;
    if (!cnt[level[u]]) level[s]=t+1;
    cnt[++level[u]]++;
    cur[u]=elast[u];
    return k;
}
signed main()
{
    //¡¾Ä£°å¡¿ÍøÂç×î´óÁ÷
    int m,u,v,w;
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    while(m--)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    bfs(t);
    while(level[s]<=t)
    {
        memcpy(cur,elast,sizeof(cur));
        ans+=augment(s,inf);
    }
    printf("%lld",ans);
}

by 约瑟夫用脑玩 @ 2021-07-20 11:27:44

以前会 SAP 现在不会了qwq。

这边重构写 Dinic。


by reveal @ 2021-07-20 11:28:24

我对这是什么编码感到好奇


by Lucifero @ 2021-07-20 11:35:53

@约瑟夫用脑玩 本质不是一样的么,跟 ISAP


by 约瑟夫用脑玩 @ 2021-07-20 11:41:13

@Gray_White 但我只看得懂 Dinic。。。

SAP 里面挂了我看不出来的


|