ZOJ 2619 && HDU 3058 - c++编程基础

t[id[i]][tot]=-n;
mat[id[i]][id[i]]=-n;
for(j=0;j int k=next[i][j];
if(flag[k]==1)continue;
mat[id[i]][id[k]]+=1;
}
}
/*printf("%d\n",tot);
printf("Matrix has %d rows and %d columns\n",tot,tot+1);
for(i=0;i for(j=0;j<=tot;j++) printf("%lld\t",mat[i][j]);
puts("");
}
puts("*******");*/
}

ll gcd(ll a,ll b){
if (b==0)
return a;
else return gcd(b,a%b);
}

bool gauss(){
int i,j,row,id;
ll maxx;
for(row=0;row maxx=abs(mat[row][row]),id=row; //这里要挑一个小的移动，如果还是大的后面会溢出或者干脆不移动也可以
for(i=row+1;i if(abs(mat[i][row] maxx=abs(mat[i][row]);
id=i;
}
//if(maxx==0)continue;
if(id!=row){
for(j=0;j<=tot;j++)
swap(mat[row][j],mat[id][j]);
}
for(i=row+1;i if(mat[i][row]!=0){
ll q=gcd(mat[i][row],mat[row][row]);
ll gb=mat[i][row]*mat[row][row]/q;

ll l1,l2;
l1=gb/mat[i][row];
l2=gb/mat[row][row];
for(j=row;j<=tot;j++)
mat[i][j]=mat[i][j]*l1-mat[row][j]*l2;
}
}

/*for(i=0;i for(j=0;j<=tot;j++) printf("%lld\t",mat[i][j]);
puts("");
}
puts("*******");*/

}
for(i=tot-1;i>=0;i--){
for(j=i+1;j mat[i][tot]-=mat[i][j]*mat[j][j];
mat[i][i]=mat[i][tot]/mat[i][i];
}
return 1;
}

int main(){
int t,T,m,i;
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&n);
pos=0,newnode();
scanf("%s",s);
insert();
makefail();
make_mat();
gauss();
printf("Case %d:\n",t);
printf("%lld\n",mat[0][0]);
if(t!=T) puts("");
}
}

ZOJ 2619 && HDU 3058 (三)