Skip to main content

Minimum cost Maxflow or mincut maxflow or Successive Shortest Path source code in C++

when there is need of minimum cost along with maximum flow then comes this problem.
Sometimes it called successive shortest path. Here is a problem for better understanding 10498

*************************************************************************************
#include<iostream>

#include<string>

#include<vector>

#include<queue>

#include<algorithm>



using namespace std;



#define MV 102



typedef long long LL;



LL  cst[MV][MV],

    cap[MV][MV],

    par[MV],dis[MV],

    source,sink,flow;



vector<int>adj[MV];



struct pq{

    LL d,n;

    void ini(LL a,LL b){n=a;d=b;}

    bool operator<(const pq &b)const{return d>b.d;}

};





bool PFS(int s,int sk)

{

    priority_queue<pq>Q;

    pq u,v;

    int i;



    memset(dis,50,sizeof dis);

    dis[1]=0;

    u.ini(1,0);

    Q.push(u);



    while(!Q.empty())

    {

        u=Q.top();Q.pop();

        for(i=0;i<(int)adj[u.n].size();i++)

            if(cap[u.n][adj[u.n][i]] && dis[u.n]+cst[u.n][adj[u.n][i]]<dis[adj[u.n][i]])

            {

                dis[adj[u.n][i]] = dis[u.n]+cst[u.n][adj[u.n][i]];

                v.ini(adj[u.n][i],dis[adj[u.n][i]]);

                Q.push(v);

                par[adj[u.n][i]]=u.n;

            }

    }



    if(dis[sk]<dis[0])  return true;

    return false;

}



void MakeResidal(int u)

{

    cst[par[u]][u]=cst[u][par[u]]=-cst[par[u]][u];

    cap[u][par[u]]++;

    cap[par[u]][u]--;

    if(u!=1)    MakeResidal(par[u]);

}



LL MinCostFlow(int s,int sk,LL f,LL lc)

{

    source=s;

    sink = sk;

    LL tt=0,cur;

    if(!f)  return 0;

    while(f && PFS(s,sk))

    {

        cur=f;

        if(f>lc)  cur=lc;

        f-=cur;

        tt+=cur*dis[sk];

        if(!f)  return tt;

        MakeResidal(sk);

    }

    return -1;

}



int main()

{

    int n,m,i,u,v;

    LL w,f,lc;

    //freopen("Data Flow.in","r",stdin);



    while(scanf("%d%d",&n,&m)==2)

    {

        for(i=1;i<=n;i++)

            adj[i].clear();

        memset(cap,0,sizeof cap);

        memset(cst,0,sizeof cst);



        while(m--)

        {

            //scanf("%d%d%lld",&u,&v,&w);   //%d -> %lld for w

            cin>>u>>v>>w;

            cst[u][v]=cst[v][u]=w;

            cap[u][v]=cap[v][u]=1;

            adj[u].push_back(v);

            adj[v].push_back(u);

        }



        //scanf("%lld%lld",&f,&lc);   //%d -> %lld

        cin>>f>>lc;



        w = MinCostFlow(1,n,f,lc);

        if(w==-1)   printf("Impossible.\n");

        //else printf("%lld\n",w);  //%d -> %lld for w

        else cout<<w<<endl;

    }

    return 0;

}

Comments

Popular posts from this blog

UDP server client in c

Server #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #include <stdio.h> #include <unistd.h> #include <errno.h> #include <string.h> #include <stdlib.h> int main() {         int sock;         int addr_len, bytes_read;         char recv_data[1024],send_data[1024];         struct sockaddr_in server_addr , client_addr;         if ((sock = socket(AF_INET, SOCK_DGRAM, 0)) == -1) {             perror("Socket");             exit(1);         }         server_addr.sin_family = AF_INET;         server_addr.sin...

My favourite writer Humayun Ahmed

There is none who can replace him.At least the standard which he create in is life time in the running literature it never be replaceable.The new generation which is all the time busy in playing PC games,chatting ,bands etc. only his writing makes them to take a glance on the literature.For example Himu and Misir ali all the time keep them on track by anti-logic and logic.They also have show-down on the novel.I myself read all of the books of Himu and Misir ali and wait for the new one to come every year.Now I have to wait for life time. Except books he makes our dirty film industry pure by his heart warming ,well versed film.Following him many new producer try to make well and good film (not the dirty one) .He also contribute our drama by his dashing drama's. In writing except romance ,logic ,anti-logic ,he also write many science fiction.His brother Sir Dr. Md. Zafar Iqbal is the man who started science fiction in bangla. The list of books: Selected novels • Lilaboti (2...

[ASTERIK] configure: error: *** uuid support not found (this typically means the uuid development package is missing)

ISSUE: Build error on Asterik , when you want test webrtc feature :) checking for uuid_generate_random in -luuid... no checking for uuid_generate_random in -le2fs-uuid... no checking for uuid_generate_random... no configure: error: *** uuid support not found (this typically means the uuid development package is missing) Fix: This issue arises due to missing of UUID generator specified by rfc4122 . +Linux sudo apt-get install uuid-dev  @Unix yum -y install libuuid-devel Asterik comes with lots of helpful script available on - asterisk/contrib/scripts/ folder of your ASTERIK source. So just use the following command on UNIX console to run the asterik pre-requisite script. contrib/scripts/install_prereq install And you are done! configuring. Now -- Make Asterik.