EK求助73,没找到实现上的问题

P3376 【模板】网络最大流

Tangent233 @ 2021-11-26 20:30:10

#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
const long long inf=1e10+10;
int n,m,s,t;
struct edge
{
    int from,to,cap,flow;
};
vector<edge> edges;
vector<int> g[maxn];
long long a[maxn],p[maxn];
void addedge(int f,int t,int c)
{
    edges.push_back(edge{f,t,c,0});
    edges.push_back(edge{t,f,0,0});
    int m=edges.size();
    g[f].push_back(m-2);
    g[t].push_back(m-1);
}
unsigned int maxflow(int s,int t)
{
    unsigned int flow=0;
    while(1)
    {
        memset(a,0,sizeof(a));
        queue<int> q;
        q.push(s);
        a[s]=inf;
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=0;i<g[x].size();i++)
            {
                edge& e=edges[g[x][i]];
                if(!a[e.to]&&e.cap>e.flow)
                {
                    p[e.to]=g[x][i];
                    a[e.to]=min(a[x],(long long)e.cap-e.flow);
                    q.push(e.to);
                }
            }
            if(a[t]) break;
        }
        if(!a[t]) break;
        for(int u=t;u!=s;u=edges[p[u]].from)
        {
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        flow+=a[t];
    }
    return flow;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main()
{/*
    freopen("P3376.in","r",stdin);
    freopen("P3376.ans","w",stdout);
*/  n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        a=read(),b=read(),c=read();
        addedge(a,b,c);
    }
    cout<<maxflow(s,t)<<endl;
    return 0;
}

怎么溢出了 贺了oiwiki的代码


by _Yoimiya_ @ 2021-11-27 11:32:35

你需要

#define int long long

|