## 10828 - Back to Kernighan-Ritchie

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

Moderator: Board moderators

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
I get the correct result for all test-cases posted here. but i still get WA. Can somebody give some more test-cases?
Maybe i get a precision error. I use Gauss method for solving system of equations. Does it make lots of errors? what's a better way?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I have a question, how many equations do we need to solve?

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
sclo wrote:I have a question, how many equations do we need to solve?
My solution solves n equations with n unknowns.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
I use Gaussian Elimination with global pivoting strategy:

Code: Select all

``````#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 128
#define xchg(x,y) (((x)==(y))||((x)^=(y),(y)^=(x),(x)^=(y)))
#define tol (1e-10)

double max( double x, double y ) { return x < y ? y : x; }

double w[N][N],x[N];

int got_input() {
int i,j,k;
if ( scanf("%d",&n) != 1 || !n )
return 0;
memset(deg,0,sizeof(deg));
while ( scanf("%d %d",&i,&j) == 2 && (--i >= 0) )
return 1;
}

void init() {
int i,j,k;

for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
w[i][j] = .0;

for ( i = 0; i < n; i++ )
for ( k = 0; k < deg[i]; k++ ) {
w[j][i] += (1.00 / deg[i]);
}

for ( i = 1; i < n; i++ )
w[i][n] = .0;

w[0][n] = -1.0;

for ( i = 0; i < n; i++ ) {
id[i] = i;
is_inf[i] = 0;
}
for ( i = 0; i < n; i++ )
w[i][i] -= 1.0;
}

int find_pivot( int m, int *r, int *c ) {
int i,j,k;
double tmp = .0;

for ( i = m; i < n; i++ )
for ( j = m; j < n; j++ )
if ( tmp < fabs(w[i][j]) ) {
tmp = fabs(w[i][j]);
if ( r && c ) *r = i, *c = j;
}
return tmp > tol;
}

void swap_cols( const int c1, const int c2 ) {
int i;
double tmp;
for ( i = 0; i < n; i++ )
tmp = w[i][c1], w[i][c1] = w[i][c2], w[i][c2] = tmp;
}

void swap_rows( const int r1, const int r2 ) {
int j;
double tmp;
for ( j = 0; j <= n; j++ )
tmp = w[r1][j], w[r1][j] = w[r2][j], w[r2][j] = tmp;
}

void elim() {
int i,j,k,t,r,c;
double cf;

for ( i = 0; i < n && find_pivot(i,&r,&c); i++ ) {
swap_cols(i,c);
swap_rows(i,r);
xchg(id[i],id[c]);
for ( t = i+1; t < n; t++ ) {
cf = (w[t][i] / w[i][i]);
for ( j = i; j <= n; j++ )
w[t][j] -= w[i][j]*cf;
}
}
}

void back() {
int i,j,k,t;
double sum;

for ( i = n-1; i >= 0 && fabs(w[i][i]) < tol; --i )
is_inf[id[i]] = 1;
for ( ;i >= 0; --i ) {
for ( sum = .0, j = n-1; j > i; --j )
if ( fabs(w[i][j]) > tol ) {
if ( is_inf[id[j]] ) {
is_inf[id[i]] = 1;
goto next;
}
else
sum += w[i][j]*x[id[j]];
}
x[id[i]] = ((w[i][n] - sum) / w[i][i]);
next: continue;
}
}

int main() {
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("10828.in","r",stdin);
#endif
while ( got_input() ) {
printf("Case #%d:\n",++ts);
init();
elim();
back();
for ( scanf("%d",&k); k-- && scanf("%d",&i) == 1 && --i >= 0; )
if ( is_inf[i] )
puts("infinity");
else
printf("%.3lf\n",x[i]+tol);
}
return 0;
}
``````
but WA. Anyone who got it with the same algo, or you used some fancy algorithms?

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
How to deal with multiple edges?

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

### Re: 10828 - Back to Kernighan-Ritchie

Hmmm, How to handle the infinity case?, My Gaussian either says (we have sol, no sol, infinite ones)
I passed all the samples with wrong judging on infinity case.
Sleep enough after death, it is the time to work.