萌新,自测数据可以过,为什么交上去会re?

P3376 【模板】网络最大流

mygr @ 2023-07-02 21:02:50

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,nums[505],from[505],x,y,z,Min=0x7fffffff,Map[505][505],Rank[505][505]; 
vector<int> p[505];//to  egde
bool vis[505],can;
long long int ans;
queue<int> into;
int bfs()
{
    into.push(s);
    vis[s]=true;
    while(!into.empty())
    {
        int now=into.front();
        if(now==t)
        {
            while(!into.empty())
            {
                into.pop();
            }
            for(int i=1;i<=n;i++)
                vis[i]=false;
            can=true;
            break;
        }
        into.pop();
        for(int i=0;i<nums[now];i++)
        {
            if(Map[now][p[now][i]]<=0)
                continue;
            int to=p[now][i];
            if(vis[to])
                continue;
            into.push(to);
            vis[to]=true;
            from[to]=now;
        }
        //cout<<"a";
    }
}
int update()
{
    int now=t,Min=0x7fffffff;
    while(now!=s)
    {
        Min=min(Min,Map[from[now]][now]);
        now=from[now];
    }
    now=t;
    ans+=Min;
    while(now!=s)
    {
        Map[now][from[now]]+=Min;
        Map[from[now]][now]-=Min;
        now=from[now];
    }
}
int main()
{
    //freopen("P3376_1.in","r",stdin);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        p[x].push_back(y);
        p[y].push_back(x);
        Map[x][y]=z;
        nums[x]++;
        nums[y]++;
    }
    can=true;
    while(can)
    {
        can=false;
        bfs();
        update();
    }
    cout<<ans;
}

by P7GAB @ 2023-09-16 11:03:22

初步观察:数组太小,bfs、update没有返回值。


|