820 - Internet Bandwidth

[nonvoid]

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;

bool read(){

	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;
	while(read()){
			printf("Network %d\nThe bandwidth is %ld.\n\n", nc, flow());
		nc++;
		clean();
	}
	
	return 0;
}

Thanks.

[serur]

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.

[nymo]

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]

THANK YOU!!!!!

[lovemagic]

somebody post some test case with output?
i m getting WA!!!

[lovemagic]

I got AC now........
as the path are bidirectional,
so m[j]+=m[j]+=w;
this is the only special case in this problem.

[Spykaj]

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;
  }
}
void addpath(long flow) {
  //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;
        addpath(flow);
        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]

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]

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]

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]

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

[mf]

You should clear array 'cap' between test cases, and

Print a blank line after each test case.

[sklitzz]

Ok, I've changed that. But still it keeps giving me WA. I have no more idea what to
do!

Code: Select all

AC...

[mf]

Test your program on an input consisting of several test cases. You'll find your error.

[sklitzz]

Thanks man! That was a really stupid error