1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 105; 7 const int INF = 2000000000; 8  9 bool Sx[maxn], Sy[maxn];10 int Lx[maxn], Ly[maxn];11 int Link[maxn];12 int W[maxn][maxn];13 int n, m;14 15 bool Find(int i) {16     Sx[i] = true;17     for(int j = 1; j <= m; j++) {18         if(!Sy[j] && Lx[i] + Ly[j] == W[i][j]) {19             Sy[j] = true;20             if(Link[j] == 0 || Find(Link[j])) {21                 Link[j] = i;22                 return true;23             }24         }25     }26     return false;27 }28 29 int KM() {30     for(int i = 1; i <= n;i++) {31         Lx[i] = 0;32         for(int j = 1; j <= m; j++) {33             Lx[i] = max(Lx[i], W[i][j]);34         }35     }36     memset(Ly, 0, sizeof(Ly));37     memset(Link, 0, sizeof(Link));38     for(int v = 1; v <= n; v++) {39         memset(Sx, 0, sizeof(Sx));40         memset(Sy, 0, sizeof(Sy));41         while(1) {42             if(Find(v)) break;43             int dmin = INF;44             for(int i = 1; i <= n; i++) {45                 if(Sx[i]) {46                     for(int j = 1; j <= m; j++) {47                         if(!Sy[j] && Lx[i] + Ly[j] - W[i][j] < dmin) {48                             dmin = Lx[i] + Ly[j] - W[i][j];49                         }50                     }51                 }52             }53             for(int i = 1; i <= n; i++) {54                 if(Sx[i]) {55                     Lx[i] -= dmin;56                     Sx[i] = 0;57                 }58             }59             for(int i = 1; i <= m; i++) {60                 if(Sy[i]) {61                     Ly[i] += dmin;62                     Sy[i] = 0;63                 }64             }65         }66     }67     int sum = 0;68     for(int i = 1; i <= n; i++) {69         sum += W[Link[i]][i];70     }71     return sum;72 }73 74 int val[maxn];75 char mat[maxn][maxn];76 int main() {77     while(scanf("%d",&n) && n) {78         memset(W, 0, sizeof(W));79         for(int i = 1; i <= n; i++) {80             scanf("%d",&val[i]);81         }82         for(int i = 1; i <= n; i++) {83             scanf("%s",mat[i]);84         }85         for(int i = 1; i <= n; i++) {86             for(int j = 0; j < n; j++) {87                 if(i == j + 1) continue;88                 if(mat[i][j] == ‘1‘) {89                     W[i][j + 1] = val[i] ^ val[j + 1];90                 }91             }92         }93         m = n;94         printf("%d\n",KM());95     }96     return 0;97 }