10594 - Data Flow

[ranban282]

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;
}

[Tutte]

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.

[x140l31]

I got WA, can anyone help me please?

code removed

[Jan]

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

[camara]

And what about this case?

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?

[Jan]

I used 'long long'.

[DJWS]

Output:
15
Impossible
15
Impossible
1500

Numbers are okay.
But there should be one period at the end of the word 'Impossible.'

[DD]

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

[DD]

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!

[calicratis19]

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.

[matheusdallrosa]

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

instead of:
4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 1
?