10330 - Power Transmission

[dip]

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

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

[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]

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]

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]

Hi fellows!

I guess you got AC by now, so I'm curious to know what had caused your WAs then?

[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.

Code: Select all

I want your help badly

[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 funny , for the outgoing flows to the supersink, I simply use the node that was supposed to be used to incoming flows!!!

[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]

[serur]

With similar algo I got AC 820-"Internet Bandwidth".
What the crucial difference between this one and that?
Please help!

[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]

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!

[serur]

Well, my next concern is biparite/complete matching.
Or I heard about something like mincost_maxflow...

[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

[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