1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <vector>  5   6 using namespace std;  7   8 class Node {  9 public: 10     int row,col; 11     int value; 12     Node (int r,int c,int v) { 13         row = r; 14         col = c; 15         value =http://www.mamicode.com/ v; 16     } 17 }; 18  19 class Matrix { 20 private: 21     int rownum,colnum; 22     int ElementNumber; 23     vector<int>rowstart; 24     vector<int>colstart; 25     vector<Node> data; 26  27 public: 28     Matrix() { 29         ElementNumber = 0; 30         rowstart.clear(); 31         colstart.clear(); 32         data.clear(); 33     } 34     ~Matrix() { 35         ElementNumber = 0; 36         rowstart.clear(); 37         colstart.clear(); 38         data.clear(); 39     } 40  41     void Start() { 42         rowstart.resize(1000); 43         colstart.resize(1000); 44         int rownumber[1000]; 45         memset(rownumber,0,sizeof(rownumber)); 46         for (int i = 0;i < ElementNumber;i++) rownumber[data[i].row]++; 47         for (int i = 1;i < rownum;i++) rowstart[i] = rowstart[i - 1] + rownumber[i - 1]; 48  49         int colnumber[1000]; 50         memset(colnumber,0,sizeof(colnumber)); 51         for (int i = 0;i < ElementNumber;i++) colnumber[data[i].col]++; 52         for (int i = 1;i < colnum;i++) { 53             colstart[i] = colstart[i - 1] + colnumber[i - 1]; 54         } 55     } 56  57     void input() { 58         cin >> rownum >> colnum; 59         for (int i = 0;i < rownum;i++) { 60             int value; 61             for (int j = 0;j < colnum;j++) { 62                 cin >> value; 63                 if (value) { 64                     data.push_back(Node(i,j,value)); 65                     ElementNumber++; 66                 } 67             } 68         } 69         Start(); 70     } 71  72     void output() { 73         int pos = 0; 74         for (int i = 0;i < rownum;i++) { 75             for (int j = 0;j < colnum;j++) { 76                 if (pos < ElementNumber && data[pos].row == i && data[pos].col == j) { 77                     cout << data[pos++].value << " "; 78                 } 79                 else cout << 0 << " "; 80             } 81             cout << endl; 82         } 83     } 84  85     void Trans_1() { 86         vector <Node> temp(data.begin(), data.end()); 87         int num = 0; 88         for (int i = 0;i < colnum;i++) { 89             for (int j = 0;j < ElementNumber;j++) { 90                 if (temp[j].col == i) { 91                     data[num].row = temp[j].col; 92                     data[num].col = temp[j].row; 93                     data[num].value =http://www.mamicode.com/ temp[j].value; 94                     num++; 95                 } 96             } 97         } 98         swap(rownum,colnum); 99         swap(colstart,rowstart);100     }101 102     void Trans_2() {103         vector <Node> temp(data.begin(), data.end());104         vector <int> start(colstart.begin(),colstart.end());105         for (int i = 0;i < ElementNumber;i++) {106             int j = start[temp[i].col] ++;107             data[j].row = temp[i].col;108             data[j].col = temp[i].row;109             data[j].value =http://www.mamicode.com/ temp[i].value;110         }111         swap(colnum,rownum);112         swap(colstart,rowstart);113     }114 115     Matrix Multi(Matrix MX) {116         Matrix C;117         if (ElementNumber * MX.ElementNumber != 0) {118             for (int i = 0;i < rownum;i++) {119                 int ctemp[colnum + 1];120                 memset(ctemp,0,sizeof(ctemp));121                 int tp;122                 if (i == rownum - 1) {123                     tp = ElementNumber;124                 }125                 else {126                     tp = rowstart[i + 1];127                 }128 129                 for (int j = rowstart[i];j < tp;j++) {130                     int k = data[j].col;131                     int t;132                     if (k == MX.rownum - 1) {133                         t = MX.ElementNumber;134                     }135                     else {136                         t = MX.rowstart[k + 1];137                     }138                     for (int l = MX.rowstart[k];l < t;l++) {139                         ctemp[MX.data[l].col] += data[j].value * MX.data[l].value;140                     }141                 }142                 for (int l = 0;l < MX.colnum;l++) {143                     if (ctemp[l]) {144                         C.data.push_back(Node(i,l,ctemp[l]));145                         C.ElementNumber++;146                     }147                 }148             }149         }150         C.rownum = rownum;151         C.colnum = MX.colnum;152         C.Start();153         return C;154     }155 };156 157 int main () {158     Matrix A;159     A.input();160     Matrix B;161     B.input();162     Matrix C = A.Multi(B);163     C.output(); 164 }