91 pts

P3376 【模板】网络最大流

Disjoint_cat @ 2023-01-20 09:26:22

难道是我当前弧假了???

核心代码:

const int N=205,M=5005;
int n,m,s,t;
int U,V;ll Cap;
int head[N],to[M<<1],nxt[M<<1],tot,nxte[N];ll cap[M<<1];
#define rev(x) ((x&1)?x+1:x-1)
void add()
{
    to[++tot]=V,cap[tot]=Cap,nxt[tot]=head[U],head[U]=tot;
    to[++tot]=U,cap[tot]=0,nxt[tot]=head[V],head[V]=tot;
}
int lev[N];bool vis[N];
void bfs()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)nxte[i]=head[i];
    queue<int>q;
    q.push(s);
    while(q.size())
    {
        int now=q.front();q.pop();
        vis[now]=1;
        for(int i=head[now];i;i=nxt[i])
        {
            int To=to[i];
            if(!cap[i]||vis[To])continue;
            lev[To]=lev[now]+1;
            q.push(To);
        }
    }
}
vector<int>E;
ll dfs(int now)
{
    if(now==t)return 1000000000000000000;
    for(int i=nxte[now];i;i=nxt[i],nxte[now]=i)
    {
        if(!cap[i]||lev[to[i]]<=lev[now])continue;
        ll flo=dfs(to[i]);
        if(flo){E.push_back(i);return min(cap[i],flo);}
    }
    return 0;
}
ll Dinic()
{
    ll ans=0;//int cnt=0;
    while(1)
    {
        //cout<<++cnt<<endl;
        bfs();
        if(!vis[t])break;
        while(1)
        {
            E.clear();
            ll flow=dfs(s);
            if(!flow)break;
            ans+=flow;
            for(int i=0;i<E.size();i++)
                cap[E[i]]-=flow,cap[rev(E[i])]+=flow;
        }
    }
    return ans;
}
void Solve()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>U>>V>>Cap;
        add();
    }
    cout<<Dinic();
}

by Disjoint_cat @ 2023-01-20 09:28:55

二刷板题还能 TLE


|