10330  Power Transmission
Moderator: Board moderators
10330 Power Transmission
I used EdmondsKarp 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 vcvf 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.
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 vcvf 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 = V1; 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..
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.
Hi fellows!
I guess you got AC by now, so I'm curious to know what had caused your WAs then?
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
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
Code: Select all
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
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.
and
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!!!
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
Code: Select all
output:
10
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!!!
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]
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
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:
and in the bfs part, you use
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.
Code: Select all
for(i=0;i<K;i++)
for(j=0;j<K;j++)
residual[i][j]=c[i][j];
Code: Select all
for(y=0;y<K;y++)
if(parents[y]==UNKNOWN && residual[x][y]>0){
enQueue(Q,y);
parents[y]=x;
}
Thank you nymo!
Look at this:
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!
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 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

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
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 EdmondsKarp 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
I try ford with dijkstra and got ac in 0.213
I try ford with bfs and got TLE(opposite to my expections)
also EdmondsKarp 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
Mostafa Saad
10330  Getting WA. Plz Hlp
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...)
Got AC at last
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
Shihab
CSE,BUET
CSE,BUET