萌新求助DinicTLE#9

P3376 【模板】网络最大流

Xqbk @ 2021-07-25 11:36:39

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=5100;
const int INF=0x3f3f3f3f;
long long n,m,s,t,u,v,c;
long long head[MAXN],nxt[MAXN<<2],to[MAXN<<2],cap[MAXN<<2],flo[MAXN<<2],cnt;
bool vis[MAXN];
int dep[MAXN],cur[MAXN];
void addEdge(int u,int v,long long c)
{
    cnt++;
    nxt[cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    cap[cnt]=c;
    flo[cnt]=0;
}
bool bfs(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    dep[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(!vis[v]&&cap[i]>flo[i])
            {
                vis[v]=1;
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    //cout<<vis[t]<<endl;
    return vis[t];
}
long long dfs(int s,int t,int u,long long a)
{
    if(u==t||a==0)
    {
        return a;
    }
    long long flow=0,f;
    cur[u]=head[u];
    for(int i=cur[u];i;i=nxt[i])
    {
        int v=to[i];
        cur[u]=i;
        if(dep[u]+1==dep[v]&&(f=dfs(s,t,v,min(a,cap[i]-flo[i])))>0)
        {
            flo[i]+=f;
            flo[i^1]-=f;
            flow+=f;
            a-=f;
            if(a==0)
            {
                break;
            }
        }
    }
    return flow;
}
long long maxFlow(int s,int t)
{
    long long flow=0;
    while(bfs(s,t))
    {
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,t,s,INF);
    }
    return flow;
}
int main()
{
    //freopen("in.txt","r",stdin);
    cin>>n>>m>>s>>t;
    cnt=1;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>c;
        addEdge(u,v,c);
        addEdge(v,u,0);
    }
    cout<<maxFlow(s,t);
}

by Xqbk @ 2021-07-25 11:37:36

邻接表可以过换前向星就不行qwq


by 绝顶我为峰 @ 2021-07-25 11:45:43

前向星常数大,有问题吗


|