迷之60分WA,求助!

P3376 【模板】网络最大流

極·郭际泽 @ 2018-12-22 09:53:20

评测记录

code:(推送-重贴标签算法)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int INF=1073741823;

struct edge
{
    int to;
    int cap;
};

struct listbase
{
    edge val;
    int next;
}net[110001];

int n,m;
int s,t;

queue<int> overflow;
int flow[110001];
int over[10001];
int h[10001];

void push(int p)
{
    int now=p;
    while(now!=-1)
    {
        edge v=net[now].val;
        int val=min(over[p],v.cap-flow[now]);
        if(val!=0 && h[p]>h[v.to])
        {
            if(over[v.to]==0 && v.to!=s && v.to!=t)
                overflow.push(v.to);
            over[p]-=val;
            over[v.to]+=val;
            flow[now]+=val;
            if(over[p]==0)
                return;
        }
        now=net[now].next;
    }
}

void remark(int p)
{
    int minh=INF;
    int now=p;
    while(now!=-1)
    {
        edge v=net[now].val;
        if(flow[now]<v.cap)
            minh=min(minh,h[v.to]);
        now=net[now].next;
    }
    h[p]=minh+1;
}

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

    for(int i=1;i<=n;i++)
        if(i!=s && i!=t)
            net[i]={{s,INF},-1};
    net[s]={{n+1,0},-1};
    m+=n;
    int last[10001];
    for(int i=1;i<=n;i++)
        last[i]=i;
    for(int i=n+1;i<=m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        if(b==s || a==t || a==b)
            continue;
        net[last[a]].next=i;
        last[a]=i;
        net[i]={{b,w},-1};
    }

    int now=s;
    while(now!=-1)
    {
        if(net[now].val.to==n+1)
        {
            now=net[now].next;
            continue;
        }
        edge v=net[now].val;
        flow[now]=v.cap;
        over[v.to]=v.cap;
        if(v.to!=t)
            overflow.push(v.to);
        now=net[now].next;
    }

    h[s]=n;
    while(!overflow.empty())
    {
        int p=overflow.front();
        overflow.pop();
        while(true)
        {
            int before=over[p];
            push(p);
            int after=over[p];
            if(before==after)
                remark(p);
            if(after==0)
                break;
        }
    }
    printf("%d\n",over[t]);
    return 0;
}

码风清奇,请见谅QwQ


|