10594 - Data Flow

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

WA

Post by ranban282 » 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;
}

Tutte
New poster
Posts: 1
Joined: Wed Feb 13, 2008 1:57 am

Post by Tutte » 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.

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 10594 - Data Flow

Post by x140l31 » Sat May 03, 2008 7:52 pm

I got WA, can anyone help me please? :(

code removed
Last edited by x140l31 on Tue May 06, 2008 12:53 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10594 - Data Flow

Post by Jan » 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
Ami ekhono shopno dekhi...
HomePage

camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm

Re: 10594 - Data Flow

Post by camara » Fri May 09, 2008 11:15 am

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?
Last edited by camara on Fri May 09, 2008 1:01 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10594 - Data Flow

Post by Jan » Fri May 09, 2008 12:08 pm

I used 'long long'.
Ami ekhono shopno dekhi...
HomePage

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 10594 - Data Flow

Post by DJWS » 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.'

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » 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 :o

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 :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10594 WA

Post by DD » 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! :)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 10594 - Data Flow

Post by calicratis19 » 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.
Heal The World

matheusdallrosa
New poster
Posts: 11
Joined: Fri Nov 08, 2013 11:04 pm

Re: 10594 - Data Flow

Post by matheusdallrosa » 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

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

Post Reply

Return to “Volume 105 (10500-10599)”