#define MAXSIZE 100
#include<stdio.h>
struct Triple
{int i,j,e;
};
struct TSMatrix
{struct Triple data[MAXSIZE+1];
 int *rpos;
 int mu,nu,tu;
};
struct TSMatrix M;
struct TSMatrix T;
struct TSMatrix Q;
void CreatSMatrix_M()
{int n=0,row,x;
 int *num;
 while(1)
   {printf("please input all data:(i,j,e)\n");
    n++;
    scanf("%d%d%d",&M.data[n].i,&M.data[n].j,&M.data[n].e);
    getchar();
    if(n>=MAXSIZE)
      break;
    printf("continue?(y/n)\n");
    if(getchar()=='n')
      break;
    getchar();
   }
 printf("please input the mu, nu and tu:\n");
 scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
 getchar();
 M.rpos=(int *)malloc((T.mu+1)*sizeof(int));
 num=(int *)malloc((T.mu+1)*sizeof(int));
 for(row=1;row<=M.mu;++row)
   num[row]=0;
 for(x=1;x<=M.tu;++x)
     ++num[M.data[x].i];
 M.rpos[1]=1;
 for(row=2;row<=M.mu;row++)
     M.rpos[row]=M.rpos[row-1]+num[row-1];
}
void CreatSMatrix_T()
{int n=0,row,x;
 int *num;
 while(1)
   {printf("please input all data:(i,j,e)\n");
    n++;
    scanf("%d%d%d",&T.data[n].i,&T.data[n].j,&T.data[n].e);
    getchar();
    if(n>=MAXSIZE)
      break;
    printf("continue?(y/n)\n");
    if(getchar()=='n')
      break;
    getchar();
   }
 printf("please input the mu, nu and tu:\n");
 scanf("%d%d%d",&T.mu,&T.nu,&T.tu);
 getchar();
 T.rpos=(int *)malloc((T.mu+1)*sizeof(int));
 num=(int *)malloc((T.mu+1)*sizeof(int));
 for(row=1;row<=T.mu;++row)
   num[row]=0;
 for(x=1;x<=T.tu;++x)
     ++num[T.data[x].i];
 T.rpos[1]=1;
 for(row=2;row<=T.mu;row++)
     T.rpos[row]=T.rpos[row-1]+num[row-1];
}
void PrintSMatrix(struct TSMatrix x)
{int n;
 printf("i j e\n");
 for(n=1;n<=x.tu;n++)
   printf("%d %d %d\n",x.data[n].i,x.data[n].j,x.data[n].e);
}
int MultSMatrix()
{int arow,tp,brow,t,p,q,ccol,n;
 int *ctemp;
 if(M.nu!=T.mu)
   return 0;
 Q.mu=M.mu;
 Q.nu=T.nu;
 Q.tu=0;
 if(M.tu*T.tu==0)
     return 1;
 else
   for(arow=1;arow<=M.mu;++arow)
     {ctemp=(int *)malloc(T.nu*sizeof(int));
      for(n=1;n<=T.nu;n++)
        ctemp[n]=0;
      Q.rpos[arow]=Q.tu+1;
      if(arow<M.mu)
        tp=M.rpos[arow+1];
      else
        tp=M.tu+1;
      for(p=M.rpos[arow];p<tp;++p)
        {brow=M.data[p].j;
         if(brow<T.mu)
           t=T.rpos[brow+1];
         else
           t=T.tu+1;
         for(q=T.rpos[brow];q<t;++q)
          {ccol=T.data[q].j;
           ctemp[ccol]+=M.data[p].e*T.data[q].e;
          }
        }
      for(ccol=1;ccol<=Q.nu;++ccol)
        if(ctemp[ccol])
          {if(++Q.tu>MAXSIZE)
             return 0;
           Q.data[Q.tu].i=arow;
           Q.data[Q.tu].j=ccol;
           Q.data[Q.tu].e=ctemp[ccol];
           }
     }
}
void main(void)
{CreatSMatrix_M();
 printf("print SMatrix M:\n");
 PrintSMatrix(M);
 CreatSMatrix_T();
 printf("print SMatrix T:\n");
 PrintSMatrix(T);
 MultSMatrix();
 printf("print SMatrix Q:\n");
 PrintSMatrix(Q);
 getchar();
}