10330 - Power Transmission

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

Moderator: Board moderators

dip
New poster
Posts: 7
Joined: Sat Nov 20, 2004 10:20 am
Location: Dhaka
Contact:

>?

Post by dip »

Hi Jalal,
My accepted codes give the same result. Good Luck :D
something .....

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

10330 Power Transmission

Post by wook »

I used Edmonds-Karp algorithm but WA.

to deal with the vertex capacity, i used two additional arrays:

vc : the vertex capacity of vertex u
vf : the current flow of vertex u

always vf <= vc

residual capacity of vertex is vc-vf then.

so, for every augumenting path P,
the flow is min{ every residual capacity of edges or vertex in P }



is this wrong?

I tried all of test data in previous board here,
but my program didn't gave the wrong one.

please, clarify me why this gave me WA,
or give me some tricky test datas.

Thanks.

Code: Select all

#include <stdio.h>
#include <vector>

using namespace std;
typedef vector<int> vi;

#define maxn 105
#define fmin(x, y) ( (x) > (y) ? (y) : (x) )

const int inf = 2147483647;
int V, E, s, t, B, D;
int c[maxn][maxn]; // capacity
int f[maxn][maxn];

int vc[maxn]; // vertex capacity
int vf[maxn]; // vertex flow

vi neigh_list[maxn];
int que[maxn];
int par[maxn];

bool input_graph()
{
	int i, x, y, z;
	if( scanf("%d", &V) != 1)
		return false;

	for(i=1; i<=V; ++i)
		scanf("%d", vc + i);

	scanf("%d", &E);
	for(i = 1; i <= V; ++ i)
		neigh_list[i].clear();

	for(i = 0; i < E; ++ i)
	{
		scanf("%d %d %d", &x, &y, &z);
		c[x][y] = z;

		neigh_list[x].push_back(y);
	}

	// source and sink
	V += 2;
	s = V-1; t = V;
	vc[s] = vc[t] = inf;

	neigh_list[s].clear();
	neigh_list[t].clear();

	// multisource, multisink
	scanf("%d %d", &B, &D);
	while(B--)
	{
		scanf("%d", &x);
		c[s][x] = inf;
		neigh_list[s].push_back(x);
	}

	while(D--)
	{
		scanf("%d", &y);
		c[y][t] = inf;
		neigh_list[y].push_back(t);
	}

	memset(vf, 0, sizeof(vf));
	return true;
}

bool path()
{
	int front, rear;
	int u, v, i, l;
	int dis[maxn] = {0,};
	front = rear = 0;

	for(i=1; i<=V; ++i)
		dis[i] = inf;

	que[++rear] = s;
	dis[s] = 0;
	par[s] = 0;

	while(front != rear)
	{
		u = que[++front];

		l = neigh_list[u].size();
		for(i=0; i<l; ++i)
		{
			v = neigh_list[u][i];
			if(vc[v] - vf[v] <= 0)
				continue;
			if(c[u][v] - f[u][v] <= 0)
				continue;

			if(dis[u] + 1 < dis[v])
			{
				dis[v] = dis[u] + 1;
				par[v] = u;
				que[++rear] = v;
			}
		}
	}

	if(dis[t] < inf)
		return true;
	return false;
}

void edmonds_karp()
{
	int u, v;
	int min;

	while( path() )
	{
		min = vc[t] - vf[t];
		for(u = par[t], v = t; v != s; u = par[u], v = par[v])
		{
			min = fmin(min, c[u][v] - f[u][v]);
			min = fmin(min, vc[u] - vf[u]);
		}
		
		vf[t] += min;
		for(u = par[t], v = t; v != s; u = par[u], v = par[v])
		{
			f[u][v] += min;
			f[v][u] -= min;
			vf[u] += min;
		}
	}

	printf("%d\n", vf[t]);
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif

	while( input_graph() )
	{
		memset(f, 0, sizeof(f));
		edmonds_karp();
		memset(c, 0, sizeof(c));
	}

	return 0;
}
Sorry For My Poor English.. :)

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo »

Hi, I am trying to solve this problem (10330: Power transmission) but i get WA. I tried all the previous I/O posted on board and it produced me correct answers. Any tricky case? Any good I/O will be a great help. Thanks...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

an easier way to deal with the vertex capacity would be to split each vertex into 2. All incomming edges would enter the first part of the vertex, and all outgoing edges would leave the second part of the vertex, where the first and second part of the vertex is connected by an directed edge with the vertex capacity.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo »

Hi sclo, I actully did the same thing you mentioned. I tried my code with different IOs and it produced the correct answer. But everytime I submit to the judge, it is a WA. Is there any special case or any trick? Can anybody post some IO so that I can check???

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Hi fellows!

I guess you got AC by now, so I'm curious to know what had caused your WAs then?
Last edited by serur on Sat Apr 14, 2012 3:29 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Well guys, pray don't look upon me as a poor thing :) but I really have no notion why this stuff gives WA in 0.154 CPU.
I want your help badly :roll:
Last edited by serur on Sat May 13, 2006 4:38 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo »

Hi, a standard trick to deal with vertex capacity is vertex splitting. Say, for node a, all incoming flow enters a new node, a1 and all outgoing flow goes out from a new node, a2. the own capacity of the node a is now between (a1, a2).i.e. node a is simulated by node a1 and a2.

For this problem, a test case posted by liulike can be a great help.

Code: Select all

input:
1
10
0
1 1
1 1
and

Code: Select all

output:
10
Though, problem statement says "Regulators connected with Barisal are not connected with Dhaka.", there is also mentioned that, "The input will start with a postive integer N ( 1<=N<=100 ) indicates the number of regulators", so, cases like N = 1 is valid case.
Anyway, I don't know if that is your problem, my cause of WA was :oops: funny :oops: , for the outgoing flows to the supersink, I simply use the node that was supposed to be used to incoming flows!!!

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Hi nymo!

Thank you for reply.
For your test both of my codes gave correct answer. Here's my code that is made as you said: regulator number t becomes a directed edge between vertices t and (t+n), supersink is vertex no.2*n+1, supersource is 0.
This one worked 0,178 CPU, but,again,I don't know :( It's a pity that OJ's responses are not like that of Saratov OJ.

[code[/code]
Last edited by serur on Sat Apr 14, 2012 3:28 pm, edited 2 times in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

With similar algo I got AC 820-"Internet Bandwidth".
What the crucial difference between this one and that?
Please help!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo »

Hi Serur, I submitted your code with different changes and everytime I got WA. I used your maxflow code, just tweaking input part. You initialized your residual matrix like this:

Code: Select all

for(i=0;i<K;i++) 
         for(j=0;j<K;j++) 
            residual[i][j]=c[i][j]; 
and in the bfs part, you use

Code: Select all

for(y=0;y<K;y++) 
         if(parents[y]==UNKNOWN && residual[x][y]>0){ 
            enQueue(Q,y); 
            parents[y]=x; 
         } 
Suppose, in the first time, you got a flow from v1 to v2(they are adjacent, c[v1][v2] > 0). But for every next time, you may have to find a path in the residual network which may run from v2 to v1, ain't it? As you have initialized your residual network, residual[v2][v1] = 0. So, your bfs will not find that path. I am not sure if it is indeed a problem, anyway, your input part is almost similar to mine but maxflow coding is somewhat different.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Thank you nymo!

Look at this:

Code: Select all

while(i!=(j=parents[i])){
		f[j][i]+=m;
		f[i][j]=-f[j][i];
		residual[j][i]=(c[j][i]-f[j][i]);
		residual[i][j]=(c[i][j]-f[i][j]);
		i=j;
	}
You see what I have added? Only one line!
You were right - the problem is really in my residuals!

Thank you :)
Keep posting!
Have a nice weekend!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Well, my next concern is biparite/complete matching. :)
Or I heard about something like mincost_maxflow...
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 »

I think this problem is too strange.
I try ford with dijkstra and got ac in 0.213
I try ford with bfs and got TLE(opposite to my expections)
also Edmonds-Karp Algorithm with bellmanford give TLE

I think the codes that get TLE has problems with infinite loops not the efficieny of the code itself, so i must think about a bug in these implementaion. I found more than 400 submission got TLE
Sleep enough after death, it is the time to work.
Mostafa Saad

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10330 - Getting WA. Plz Hlp

Post by shihabrc »

Hi all,

I'm getting WA in this prob. I've used EKarp MaxFlow to solve it. I've splitted each vertex(other than source and sink) in two and have places a edge between them having capacity equal to the given node capacity. I've tested my code with several inputs (also the ones given in prev posts), and it gave correct result.
Plz some1 hlp.(I/O, suggestions, anything...)

Code: Select all

//Cut after AC
Got AC at last
Shihab
CSE,BUET

Post Reply

Return to “Volume 103 (10300-10399)”