Cod sursa(job #2642484)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 15 august 2020 16:03:36
Problema Flux maxim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>
using namespace std;
struct Dinic
{
    struct edge
    {
        int flow ,to , next;
    };
    int s, d;
    vector<edge> edges;
    vector<int> dist , adia , at;
    void addedge(int from ,int to , int cap)
    {
        edges.push_back({cap , to , adia[from]});
        adia[from] = edges.size() - 1;
        edges.push_back({0 , from , adia[to]});
        adia[to] = edges.size()-1;
    }

    bool bfs()
    {
        queue<int>q;
        fill (dist.begin(), dist.end() , 1e9);
        dist[s] = 1;
        q.push(s);
        while(!q.empty())
        {
            int att = q.front();
            q.pop();
            int r = att;
            att  = adia[att];
            while(att != - 1)
            {
                edge m = edges[att];
                if(dist[m.to]>dist[r] + 1 && m.flow)
                {
                    dist[m.to]  =dist[r] + 1;
                    q.push(m.to);
                }
                att = m.next;
            }
        }
        return dist[d] != 1e9;
    }
    int dfs(int nod ,int flux)
    {
        if( nod == d)
            return flux;
        while(at[nod]!=-1)
        {
            int f;
            edge &e = edges[at[nod]];
            if(dist[e.to]==dist[nod]+ 1 && e.flow && (f = dfs(e.to , min(flux,e.flow))))
            {
                e.flow -= f;
                edges[at[nod]^1].flow+=f;
                return f;
            }
            at[nod] = e. next;
        }
        return 0;
    }

    int GetFlow()
    {
        int f = 0;
        while(bfs())
        {
            at = adia;
            int x = dfs(s,1e9);
            while(x)
            {f += x;
            x=dfs(s,1e9);
            }
        }
        return f;
    }
        Dinic(int n ,int s1 , int d1 )
    {
        s = s1 ;
        d = d1 ;
        dist = adia = at = vector<int>(n+ 2, -1);
    }
};
int main()

{
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    int n,m;
    cin>>n>>m;
    Dinic g(n,1,n);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g.addedge(a,b,c);
    }
    int res=g.GetFlow();
    cout<<res;
    return 0;
}