求助, TLE 64

P3376 【模板】网络最大流

nothing__ @ 2022-07-15 09:46:26


#include<iostream>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct edge{int x, y, c, pre, other;}a[41000];int alen, last[21000], h[21000], st, ed;
void  ins(int x, int y, int c)
{
    a[++alen]=edge{x, y, c, last[x], alen+1};last[x]=alen;
    a[++alen]=edge{y, x, 0, last[y], alen-1};last[y]=alen;
}
bool bh()
{
    memset(h, 0, sizeof(h)); h[st]=1;
    queue<int>q;q.push(st);
    while(!q.empty())
    {
        int x=q.front();
        for(int k=last[x];k>0;k=a[k].pre)
        {
            int y=a[k].y;
            if(h[y]==0&&a[k].c>0)
            {
                h[y]=h[x]+1; 
                q.push(y);
            }
        }
        q.pop();
    }
    return h[ed]>0;
}
int findflow(int x, int f)
{
    if(x==ed) return f; 
    int sx=0;
    for(int k=last[x];k>0;k=a[k].pre)
    {
        int y=a[k].y;
        if(a[k].c>0&&sx<f&&h[y]==(h[x]+1)) 
        {
            int sy=findflow(y, min(a[k].c, f-sx));
            a[k].c-=sy; a[a[k].other].c+=sy;
            sx+=sy;
        }
    }
    if(sx==0) h[x]=0;
    return sx;
}
int main()
{
    int n, m;
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    alen=0;memset(last, 0, sizeof(last));
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        ins(x, y, c);
    }
    long long s=0;
    while(bh()) 
    {
        s+=findflow(st, 0x15f);
    }
    printf("%d\n", s);
    return 0;
}

by nothing__ @ 2022-07-15 09:52:31

我们老师教的


by nothing__ @ 2022-07-15 09:53:50

他pop的是x吧?好像


by nothing__ @ 2022-07-15 09:54:58

@AFewSuns


|