## 820 - Internet Bandwidth

Moderator: Board moderators

nonvoid
New poster
Posts: 3
Joined: Wed Mar 15, 2006 7:44 pm
I keep getting WA on this problem. I spent hours testing my code, but no luck. I used simple preflow push algorithm. Can anyone spot what I did wrong?

Code: Select all

``````#include "stdio.h"
#include "stdlib.h"

#define MAXN 501

long C[MAXN][MAXN], F[MAXN][MAXN], E[MAXN], H[MAXN];
int N;
int S, T, CC;

scanf("%d", &N);

if(!N)
return 0;
int a, b, c;
scanf("%d%d%d", &S, &T, &CC);
for(int i = 0; i < CC; i++){
scanf("%d%d%d", &a, &b, &c);
C[a][b] += c;
C[b][a] = C[a][b];

}
H[S] = N;
return 1;
}

long flow(){
int i, j;
long tp;
for(i = 1; i <= N; i++)
if(S != i && C[S][i])
F[S][i] = C[S][i], F[i][S] = -C[S][i], E[i] = C[S][i];
while(1){
for(i = 1; i <= N; i++){
if(i == S || i == T)
continue;
if(E[i])
break;
}
if(i >= N)
break;
for(j = 1; j <= N; j++)
if(C[i][j] > F[i][j] && H[j] + 1 == H[i])
break;

if(j <= N){
tp = E[i] > C[i][j] - F[i][j] ? C[i][j] - F[i][j] : E[i];
E[i] -= tp;
E[j] += tp;
F[i][j] += tp;
F[j][i] -= tp;
}
else{
tp = 1000000;
for(j = 1; j <= N; j++)
if(C[i][j] > F[i][j] && H[j] < tp)
tp = H[j];
H[i] = 1 + tp;
}
}
return E[T];
}
/*
void gen(){
FILE *fo = fopen("820.in", "w");
int N = 200;
int M = 30000;
fprintf(fo, "%d\n", N);
fprintf(fo, "%d %d %d\n",1, N, M);
for(int i = 0; i < M;) {
int a = rand()%200 + 1, b = rand()%200 + 1;
if(a!=b){
fprintf(fo, "%d %d %d\n", a, b, rand()%1000);
i++;
}
}
fclose(fo);
}
*/
void clean(){
int i, j;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
C[i][j] = F[i][j] = 0;
for(i = 1; i <= N; i++)
E[i] = H[i] = 0;
}
int main(){
//gen();
//return 0;
#ifndef ONLINE_JUDGE
freopen("820.in", "r", stdin);
freopen("820.out", "w", stdout);
#endif
int nc = 1;
printf("Network %d\nThe bandwidth is %ld.\n\n", nc, flow());
nc++;
clean();
}

return 0;
}
``````
Thanks.

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

This is my first network flow, and therefore I hadn't scrupled to send here my code:

Code: Select all

``thank you nymo!``
The above code gives me WA in 0.092 CPU, so I'm inclined to think that there is some subtle moment of which I myself isn't clever enough to conceive. I implemented Ford-Fulkerson as it's explained in "Bible".
Every comment will be apreciated, for I'm quite of an opinion that very often a tiny hint from you == the whole book.
Last edited by serur on Thu May 11, 2006 6:45 am, edited 1 time in total.

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

### TO SERUR...

Change just one line...

Code: Select all

``````/*
c[i][j]=max(c[i][j],v);
*/ with
c[i][j] += v;
``````
If there are multiple edges, it always increases the capacity , no need to take the biggest one[ in fact, it is wrong.]

I got ACC in 0.092s with this only change.

CHEERS

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am
somebody post some test case with output?
i m getting WA!!!
khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am
I got AC now........
as the path are bidirectional,
so m[j]+=m[j]+=w;
this is the only special case in this problem.
khobaib

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

### 820 - Internet Bandwidth

Code: Select all

``````#include <cstdio>

long n;
long graph[150][150];
bool isthere[150];
long p,k,max;
long stack[150],top;
bool returntos;

void printstack() {
printf("stack:");
for (long i=0; i<top; ++i) printf("%ld ",stack[i]);
printf("\n");
}
void istherefalse(){
for(long i=0; i<150; ++i) isthere[i]=false;
}
void clearvar() {
long i,j;
istherefalse();
top=0;
for(i=0; i<150; ++i) {
stack[i]=0;
for(j=0; j<150; ++j)
graph[i][j]=0;
}
}
//printf("Path was found %ld\n",flow);
for(--top; top; --top){
graph[stack[top]][stack[top-1]]+=flow;
graph[stack[top-1]][stack[top]]-=flow;
}
istherefalse();
max+=flow;
returntos=true;
top=1;
stack[0]=p;
isthere[p]=true;
}

long findpath(long flow) {
long i,old;
//printf("findpath %ld\n", top);
//printstack();
for(i=1; i<=n; ++i) {
if(graph[stack[top-1]][i] && !isthere[i]) {
if(i==k) {
flow<?=graph[stack[top-1]][k];
stack[top++]=i;
break;
}
else {
old=flow;
flow<?=graph[stack[top-1]][i];
isthere[i]=true;
stack[top++]=i;
findpath(flow);
if(returntos)break;
--top;
isthere[i]=false;
flow=old;
}
}
}
}
long maxflow() {
long x;
long INF=999999999;
max=0;
stack[top++]=p;
isthere[p]=true;
returntos=true;
while(returntos) {
returntos=false;
x=findpath(INF);
}
return max;
}
void solve() {
long il,i,w1,w2,flow;
scanf("%ld%ld%ld",&p,&k,&il);
for(i=0; i<il; ++i) {
scanf("%ld%ld%ld",&w1,&w2,&flow);
graph[w1][w2]=flow;
graph[w2][w1]=flow;
}
flow=maxflow();
printf("The bandwidth is %ld.\n\n", flow);
}
int main() {
long i=1;
scanf("%ld",&n);
while(n) {
clearvar();
printf("Network %ld\n",i++);
solve();
scanf("%ld",&n);
}
return 0;
}
``````
HELP !

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You have TLE because your findpath() functions essentially uses backtracking to find augmenting paths.

Try for example the input, generated by

Code: Select all

``````#include <cstdio>
int main() {
int n = 50;
printf("%d\n1 %d %d\n", n, n, (n-1)*(n-2)/2);
for (int i = 1; i <= n-1; i++)
for (int j = i+1; j <= n-1; j++)
printf("%d %d %d\n", i, j, 1);
printf("0\n");
}
``````

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Hi,
I've just started figuring out how max flow works. I'm having trouble with this task because the graph is not directed and I thought this was required for max flow. Can anybody explain how does this work? ( max flow with bidirectional edges ).

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Just replace each undirected edge (x, y) of capacity c by a pair of directed edges x->y and y->x both of capacity c.

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
OK I did that and I still keep getting WA. I thought that it might be that I
implemented the max flow wrong so I copied
Igor Naverniouk's code and still get WA. Please check it out.

Code: Select all

`````` AC...
``````
Last edited by sklitzz on Sat Aug 04, 2007 10:49 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You should clear array 'cap' between test cases, and
Print a blank line after each test case.

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Ok, I've changed that. But still it keeps giving me WA. I have no more idea what to
do!

Code: Select all

``````AC...
``````
Last edited by sklitzz on Sat Aug 04, 2007 10:49 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Test your program on an input consisting of several test cases. You'll find your error.

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Thanks man! That was a really stupid error