萌新求助 #9#10 超时

应该是无弧优化的Dinic。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int n,m,s,t;
struct edge
{
    int to,next;
    long long dis;
}e[1000005];
int cnt=1,head[1000005];
int add(int x,int y,long long z)
{
    cnt++;
    e[cnt].to=y;
    e[cnt].dis=z;
    e[cnt].next=head[x];
    head[x]=cnt;
    return 0;
}
int d[1000005];
int bfs()
{
    queue<int>q;
    q.push(s);
    d[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(d[v]||!e[i].dis)continue;
            d[v]=d[u]+1;
            q.push(v);
        }
    }
    return d[t];
}
long long dfs(int x,long long flew)
{
    long long ans=0;
    if(x==t)return flew;
    for(int i=head[x];i&&flew;i=e[i].next)
    {
        int v=e[i].to;
        if(d[v]!=d[x]+1||!e[i].dis)continue;
        long long res=dfs(v,min(flew,e[i].dis));
        e[i].dis-=res;
        e[i^1].dis+=res;
        flew-=res;
        ans+=res;
    }
    if(flew==0)d[x]=0;
    return ans;
}

signed main()
{
    int i;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++)
    {
        int x,y;
        long long z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,0);
    }
    long long ans=0;
    while(bfs())
    {
        ans+=dfs(s,1e18);
        memset(d,0,sizeof(d));
    }
    cout<<ans;
    return 0;
}

谢谢巨佬。