|
|
back to boardI hate this kind of problems I cant find something wrong with my program but I get WA?Can you give me some test? #include <stdio.h> int i,j,n,m,k; int gasit; int din[2][155]; long int v[155][155]; int fl[155][155]; void readdata() { FILE *f=stdin; fscanf(f,"%d",&n); for (i=1;i<=n;i++) for (j=1;j<=n;j++) fscanf(f,"%d",&v[i][j]); for (j=1;j<=n;j++) { long int tot=0; for (i=1;i<=n;i++) tot+=v[i][j]; for (i=1;i<=n;i++) v[i][j]=tot-v[i][j]; } for (i=1;i<=n;i++) fl[i][0]=1,fl[n+1][i]=1; fclose (f); } void findpath() { long int d[2][155]; int s[2][155]; for (i=0;i<=n+2;i++) d[0][i]=1000000000,d[1][i]=1000000000,din[0][i] =0,din[1][i]=0,s[0][i]=0,s[1][i]=0; d[1][0]=0; for (i=1;i<=2*n+1;i++) { j=0; int min=n+2; int h=0; for (j=1;j<=n+1;j++) if (d[h][j]<d[h][min]&&s[0][j]==0) min=j; for (j=0;j<=n;j++) if (d[1][j]<d[h][min]&&s[1][j]==0) min=j,h=1; if (min==n+2) break; for (j=1;j<=n+1;j++) { if (fl[min][j]==0&&h==0&&d[(h+1)%2][j]>d[h][min]+v[min][j]) { if (j==n+1) gasit=1; din[(h+1)%2][j]=min; d[(h+1)%2][j]=d[h][min]+v[min][j]; } if (fl[j][min]==1&&h==1&&d[0][j]>d[1][min]-v[j][min]) { if (j==n+1) gasit=1; din[(h+1)%2][j]=min; d[(h+1)%2][j]=d[h][min]-v[j][min]; } } s[h][min]=1; } } void solve() { gasit=1; while (gasit==1) { gasit=0; findpath(); if (gasit==0) break; fl[n+1][din[0][n+1]]=0; int h=1; i=din[0][n+1]; while (i!=0) { if (h==0) fl[i][din[0][i]]=0; if (h==1) fl[din[1][i]][i]=1; i=din[h][i]; h=(h+1)%2; } } } void writedata() { long int tot=0; for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (fl[i][j]==1) tot+=v[i][j]; printf("%ld",tot); } void main() { readdata(); solve(); writedata(); } |
|
|