I'm new to min cost flow problems and I'm getting WA. The approach I follow is this:
1. Find the augumenting path which has the shortest path (Dijkstra) . Then, I remove the used edge u-v. (However, the edge v-u remains).
2. Continue till I get the desired flow.
This works on all the test cases posted on the forum.
Now, many posters have said that they've used Bellman Ford Algorithm. Why do we need to use it? Or is it that the time (cost) can be negative?
Can anyone give test cases that break the code?
Code: Select all
//does not work if source = sink
//for multiple paths, total up the costs and add to the vertex
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
#include<cassert>
#define black 0
#define gray 1
#define white 2
using namespace std;
const long long inf =(long long) 1000000000 *(long long) 1000000000;
void dijkstra(vector<vector<long long> > & v,unsigned s,vector <long long> & d, vector<long long> & prev,vector<vector<long long> > m)//v is the cost matrix, m is the flow matrix
{
vector<long long> vset;
d.assign(v.size(),inf);
prev.assign(v.size(),-1);
set<pair<long long,long long> > q;
d[s]=0;
q.insert(make_pair(0,s));
for(unsigned i=0;i<v.size();i++)
{
if(i!=s)
q.insert(make_pair(inf,i));
}
while(!q.empty())
{
pair<long long,long long> top=*(q.begin());
if(top.first==inf)
break;
q.erase(q.begin());
long long vertex=top.second;
for(unsigned i=0;i<v[vertex].size();i++)
{
if(m[vertex][i]!=0)
{
long long v2=i;
long long cost=v[vertex][i];
if(d[v2]>d[vertex]+cost)
{
q.erase(q.find(make_pair(d[v2],v2)));
d[v2]=d[vertex]+cost;
q.insert(make_pair(d[v2],v2));
prev[v2]=vertex;
}
}
}
}
}
vector<vector<long long> > ford_fulkerson(vector<vector<long long> > v, vector<vector<long long> > cost,long long s,long long t,long long total_flow,long long unit_flow)//v is the flow(capacity) matrix, s=source, t is the sink, cost is the cost matrix
{
vector<long long> temp(v.size(),0);
vector<vector<long long> > f(v.size(),temp);
while(total_flow >0)
{
vector<long long> d(v.size()),prev(v.size());
dijkstra(cost,s,d,prev,v);
long long minc=inf;
long long temp=t;
if(prev[t]==-1)
break;
//here all the nodes have unit capacity
// cout<<d[temp]<<endl;
while(prev[temp]!=-1)
{
minc=min(minc,v[prev[temp]][temp]);
temp=prev[temp];
}
temp=t;
long long t_val=min(minc,total_flow);
while(prev[temp]!=-1)
{
f[temp][prev[temp]]-=t_val;
f[prev[temp]][temp]+=t_val;
v[temp][prev[temp]]+=t_val;
v[prev[temp]][temp]-=t_val;
temp=prev[temp];
}
total_flow-=unit_flow;
}
return f;
}
int main()
{
int n,e;
while(cin>>n>>e)
{
vector<vector<long long> > v(n,vector<long long>(n,0)),cost(n,vector<long long>(n,-1));
for(int i=0;i<e;i++)
{
long long u,v1;
long long c;
scanf(" %Ld %Ld %Ld",&u,&v1,&c);
v[u-1][v1-1]=1;
v[v1-1][u-1]=1;
cost[u-1][v1-1]=c;
cost[v1-1][u-1]=c;
}
long long desired_flow,unit_flow;
cin>>desired_flow>>unit_flow;
for(int i=0;i<v.size();i++)
{
for(int j=0;j<v.size();j++)
{
v[i][j]*=unit_flow;
}
}
vector<vector<long long> > ans=ford_fulkerson(v,cost,0,n-1,desired_flow,unit_flow);
/* for(long long i=0;i<ans.size();i++)
{
for(long long j=0;j<ans.size();j++)
{
cout<<ans[i][j]<<" ";
}
cout<<endl;
}*/
long long total_flow=0;
for(int i=0;i<ans.size();i++)
{
total_flow+=ans[0][i];
}
if(total_flow < desired_flow)
printf("Impossible.\n");
else
{
long long flow_cost=0;
for(int i=0;i<ans.size();i++)
{
for(int j=0;j<ans.size();j++)
{
if(ans[i][j]>0)
flow_cost+=(ans[i][j]*cost[i][j]);
//cout<<ans[i][j]<<" "<<cost[i][j]<<endl;
}
}
printf("%Ld\n",flow_cost);
}
}
return 0;
}