bnuoj 20838 Item-Based Recommendation （模拟）

http://www.bnuoj.com/bnuoj/problem_show.php?pid=20838

【题意】：

　　有点长，略。

【code】：

　　

 #include <iostream>

 #include <stdio.h>

 #include <string>

 #include <string.h>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 double rat[][];

 double drat[][];

 struct Nod

 {

     int id;

     double rt;

 }node[];

 int m,n;

 bool cmp(Nod a,Nod b)

 {

     return a.rt>b.rt;

 }

 double getAns(int a,int b)

 {

     int i;

     double sum=;

     for(i=;i<=n;i++)

     {

         if(rat[i][a]>&&rat[i][b]>)

         {

             sum+=(rat[i][a]-rat[i][b])*(rat[i][a]-rat[i][b]);

         }

     }

     return 1.0/(sum+);

 }

 void getDrat()

 {

     int i,j;

     for(i=;i<=m;i++)

     {

         drat[i][i]=;

         for(j=i+;j<=m;j++)

         {

             drat[i][j]=drat[j][i]=getAns(i,j);

         }

     }

 }

 int main()

 {

     int c;

     scanf("%d%d%d",&n,&m,&c);

     memset(rat,,sizeof(rat));

     while(c--)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         scanf("%lf",&rat[a][b]);

     }

     getDrat();

     int x;

     while(~scanf("%d",&x))

     {

         printf("Recommendations for user %d:\n",x);

         int i,cnt=,j;

         double down=,up=;

         for(i=;i<=m;i++)

         {

             if(rat[x][i]==)//i=6

             {

                 down=,up=;

                 for(j=;j<=m;j++)

                 {

                     if(rat[x][j]>)

                     {

                         down+=drat[i][j];

                         up+=drat[i][j]*rat[x][j];

                     }

                 }

                 node[cnt].id = i;

                 node[cnt].rt = up/down;

                 cnt++;

             }

         }

         sort(node,node+cnt,cmp);

         for(i=;i<cnt&&i<;i++)

         {

             printf("%d %.3lf\n",node[i].id,node[i].rt);

         }

         putchar();

     }

     return ;

 }