[HDOJ3359 Kind of a Blur]高斯消元、例题

【题目大意】

给定一个矩阵，A[i][j]=满足abs(i-ii)+abs(j-jj)<=d的T[ii][jj]的平均数。

让你还原成T[i,j]

【算法分析】

列方程，高斯消元。

【其它】

WA很多次，需要注意的是：消元时，那个rate必须是主元的那行做分母，否则有些情况下不行。。。

为什么会这样暂时不是很清楚，等下再YY一下。。。

【CODE】

#include #include #include #include #include using namespace std;

int m,n,d,cnt[122],pos[12][12];
double q[12][12],a[122][122],x[122];

bool input(){
scanf("%d%d%d",&n,&m,&d);
if (!n && !m && !d) return false;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%lf",&q[i][j]);
return true;
}

void init(){
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
memset(x,0,sizeof(x));
int i,j,ii,jj,tmp=1;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++,tmp++)
pos[i][j]=tmp;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
for (ii=1;ii<=m;ii++)
for (jj=1;jj<=n;jj++)
if (abs(ii-i)+abs(jj-j)<=d){
cnt[pos[i][j]]++;
a[pos[i][j]][pos[ii][jj]]=1.0;
}
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
a[pos[i][j]][m*n+1]=q[i][j]*cnt[pos[i][j]];
}

void guass(){
int i,j,k; double sum,rate;
for (k=1;k for (i=k,j=k;i<=n;i++) j=fabs(a[i][k])>fabs(a[j][k])?i:j;
for (i=k;i<=n+1;i++) swap(a[j][i],a[k][i]);
for (i=k+1;i<=n;i++)
for (rate=a[i][k]/a[k][k],j=k;j<=n+1;j++)
a[i][j]-=a[k][j]*rate;
/* if (a[i][k]!=0)
for (rate=a[k][k]/a[i][k],j=k;j<=n+1;j++)
a[i][j]=a[i][j]*rate-a[k][j];
这样写是错的！！！！！！！！！！！！
*/
}
for (i=n;i>=1;i–){
for (sum=0,j=i+1;j<=n;sum+=a[i][j]*x[j],j++);
x[i]=(a[i][n+1]-sum)/a[i][i];
}
}

void output(){
for (int i=1;i<=m;i++,printf("n"))
for (int j=1;j<=n;printf("%8.2lf",x[pos[i][j]]),j++);
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int Tc=0;
while (input()){
if (Tc) printf("n");
Tc++;
init();
n*=m;
guass();
n/=m;
output();
}
}