Page 3 of 3

### WA

Posted: Fri Sep 28, 2007 6:43 pm
Hi,
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;
}
``````

Posted: Wed Feb 13, 2008 2:08 am
Can anyone post any more test data for this problem? I already checked testcases posted here and my program gives valid answers. There's probably a silly little possibility which I miss by some way.

I use Ford-Bellman algorithm for computing cheapest augmenting paths.

### Re: 10594 - Data Flow

Posted: Sat May 03, 2008 7:52 pm
I got WA, can anyone help me please?

code removed

### Re: 10594 - Data Flow

Posted: Sun May 04, 2008 1:06 am
Check the case.

Input:

Code: Select all

``````8 11
1 2 0
1 3 0
1 4 0
5 8 0
6 8 0
7 8 0
2 6 1
3 7 1
2 5 2
3 6 2
4 7 2
3 1``````
Output:

Code: Select all

``6``

### Re: 10594 - Data Flow

Posted: Fri May 09, 2008 11:15 am

10 10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
8 9 10
10 2 12
2 7 1
3 9 0
1 1
10 10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
8 9 10
10 2 12
2 7 1
3 9 0
5000 800
10 3
1 2 3
2 3 4
10 2 12
1 1
2 1
2 2 1
1 800
10 10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
8 9 10
10 2 12
2 7 1
3 9 0
100 800

Output:
15
Impossible
15
Impossible
1500

I still get WA. I only use unsigned long long in the time accumulator. Does anyone have an idea of the actual limits of K and of the maximum value for time in a link?

### Re: 10594 - Data Flow

Posted: Fri May 09, 2008 12:08 pm
I used 'long long'.

### Re: 10594 - Data Flow

Posted: Sat Aug 23, 2008 3:06 pm
camara wrote:Output:
15
Impossible
15
Impossible
1500
Numbers are okay.
But there should be one period at the end of the word 'Impossible.'

### Re:

Posted: Fri Jan 22, 2010 3:48 am
InOutMoTo wrote:
Per wrote:Ah OK, then I see why you need it. I just used Ford-Fulkerson, but augment paths using Bellman-Ford instead of DFS/BFS (not sure what Successive Shortest Path Algorithm is, but it sounds like something similar). It wasn't fast, but it worked.
I also use Ford-Fulkerson implemented with Bellman-Ford method.
However, I got TLE.

Since there won't be negative egdes,
I turn Bellman-Ford into Dijkstra method.

This time I got WA.
Can someone help

ps: I pass the test case in previous page.
In fact, this problem do contain edges with negative costs. Therefore, if you want to use Dijkstra to speed up your algorithm, you need to use the technique in Johnson's algorithm (a kind of variation of Dijkstra algorithm).

Good luck

### Re: 10594 WA

Posted: Fri Jan 22, 2010 4:04 am
kane116 wrote:Would someone give me some test case?
I think my algo is correct, I solve it as Min Cost Max Flow problem.
Here is the idea:
- The time is the cost of flowing on that edge.
- Capicity of the edge is set to K.
- While there exist an shortest augmenting path
(Use Dijkstra to find the shorest augmenting path)
* Update the flow of edge on the path
* Add the cost of flowing on this path to the total
It is basically a Ford-Fulkerson method, and use Dijkstra to find the augmenting path.

Here is the code.

Code: Select all

``````#include <cstdio>
#include <string>
#include <climits>
#define min(A, B) (A < B ? A : B)
#define ARR 200

long long int n, D, K;
long long int weg[ARR][ARR], cap[ARR][ARR], flw[ARR][ARR];
long long int cost;

bool dijk(long long int s, long long int t) {
long long int dis[ARR], pre[ARR], vis[ARR];
memset(dis, 0, sizeof(dis));
memset(pre, 0, sizeof(pre));
memset(vis, 0, sizeof(vis));
for (long long int i = 0; i < n; i++) {
dis[i] = INT_MAX;
pre[i] = -1;
vis[i] = false;
}
dis[s] = 0;
for (long long int i = 0; i < n; i++) {
long long int mn = INT_MAX, u = -1;
for (long long int j = 0; j < n; j++)
if (! vis[j] && dis[j] < mn) {
mn = dis[j];
u = j;
}
if (u != -1) {
vis[u] = true;
for (long long int v = 0; v < n; v++)
if (weg[u][v] && dis[v] > dis[u] + weg[u][v] && cap[u][v] - flw[u][v]) {
dis[v] = dis[u] + weg[u][v];
pre[v] = u;
}
}
}
if (pre[t] == -1)       return false;
long long int flow = INT_MAX;
for (long long int u = t; u != s; u = pre[u])
flow = min(flow, cap[pre[u]][u] - flw[pre[u]][u]);
for (long long int u = t; u != s; u = pre[u]) {
flw[pre[u]][u] += flow;
flw[u][pre[u]] -= flow;
}
cost += dis[t] * min(D, flow);
D -= min(D, flow);
return true;
}

int main() {
long long int t;
while (scanf("%lld%lld", &n, &t) != EOF) {
memset(weg, 0, sizeof(weg));
memset(cap, 0, sizeof(cap));
memset(flw, 0, sizeof(flw));
for (long long int i = 0; i < t; i++) {
long long int a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);      a--;    b--;
cap[a][b] = cap[b][a] = 1;
weg[a][b] = weg[b][a] = c;
}
scanf("%lld%lld", &D, &K);
for (long long int i = 0; i < n; i++)
for (long long int j = 0; j < n; j++)
if (cap[i][j])  cap[i][j] = K;
cost = 0;
while (D && dijk(0, n - 1));
if (! D)        printf("%lld\n", cost);
else printf("Impossible.\n");
}
return 0;
}
``````
Your algorithm does not consider the case where edge cost are negative.
Although this problem would not give you inputs with negative edges directly, your flow algorithm would encounter negative edges if it want to cancel the previous flow in opposite direction.

By the way, your program cannot pass the test case in this thread. Try to find your bugs by testing it!

### Re: 10594 - Data Flow

Posted: Tue Oct 11, 2011 9:55 pm
No need to use jonson's algorithm. The graph may contain negative edges due to its modification for flow. But it wont have any negative cycle. So straight forward dijkstra will do.

### Re: 10594 - Data Flow

Posted: Thu Nov 12, 2015 1:26 am
HI, the first case on the PDF, shouldn't be:
4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10