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...

[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.

Video Conferencing Project in Java Source Code

My video conferencing project was completed as 300 project for 3rd year.It is not totally completed. There is some bug in here.To solve these bugs and to help other students this project is open.It is first try to make a project open source in this way so it can be modified.Any kind of question against this project will be answered. As this project was created in 3rd year 1st semester and now i nearly completed my BSc. so there will be little description about this.I will try to describe every class and function later when i get the chance.   For more details and how to build and run go to this link   in github.com . Latest code and binary release : VideoConference-v1.1 Older code and binary release : VideoConference-v1.0 Fix: 1. When in Video chat the Text chat option hanged for good. ################################################################################# FEATURE #############################################################################...