裸的KM吧。
1 #include2 #include 3 #include 4 #include 5 #define maxn 105 6 #define INF 1<<30 7 using namespace std; 8 9 struct KM{ 10 vector G[maxn]; 11 int W[maxn][maxn],n; 12 int Lx[maxn],Ly[maxn]; 13 int left[maxn]; 14 bool S[maxn],T[maxn]; 15 16 void init(int n) 17 { 18 this->n = n; 19 for(int i = 0;i < n;i++) G[i].clear(); 20 memset(W,0,sizeof(W)); 21 } 22 23 void add_edge(int u,int v,int w) 24 { 25 G[u].push_back(v); 26 W[u][v] = w; 27 } 28 29 bool match(int i) 30 { 31 S[i] = true; 32 for(int k = 0;k < G[i].size();k++) 33 { 34 int j = G[i][k]; 35 if(Lx[i] + Ly[j] == W[i][j] && !T[j]) 36 { 37 T[j] = true; 38 if(left[j] == -1 || match(left[j])) 39 { 40 left[j] = i; 41 return true; 42 } 43 } 44 } 45 return false; 46 } 47 void update() 48 { 49 int a = INF; 50 for(int i = 0;i < n;i++) if(S[i]) 51 for(int k = 0;k < G[i].size();k++) 52 { 53 int j = G[i][k]; if(!T[j]) 54 a = min(a,Lx[i] + Ly[j] - W[i][j]); 55 } 56 for(int i = 0;i < n;i++) 57 { 58 if(S[i]) Lx[i] -= a; 59 if(T[i]) Ly[i] += a; 60 } 61 } 62 63 void solve() 64 { 65 for(int i = 0;i < n;i++) 66 { 67 Lx[i] = *max_element(W[i],W[i]+n); 68 left[i] = -1; 69 Ly[i] = 0; 70 } 71 for(int i = 0;i < n;i++) 72 { 73 while(1) 74 { 75 for(int j = 0;j < n;j++) S[j] = T[j] = 0; 76 if(match(i)) break; 77 else update(); 78 } 79 } 80 } 81 }; 82 KM solver; 83 int val[maxn]; 84 int main(){ 85 int n; 86 while(scanf("%d",&n),n){ 87 solver.init(n); 88 for(int i = 0;i < n;i++) 89 scanf("%d",&val[i]); 90 char str[105]; 91 for(int i = 0;i < n;i++){ 92 scanf("%s",str); 93 for(int j = 0;j < n;j++){ 94 if(str[j] == '1'){ 95 solver.add_edge(i,j,val[i]^val[j]); 96 }else{ 97 solver.add_edge(i,j,0); 98 } 99 }100 }101 solver.solve();102 int ans = 0;103 for(int i = 0;i < n;i++){104 if(solver.left[i] != -1)105 ans += solver.W[solver.left[i]][i];106 }107 printf("%d\n",ans);108 }109 return 0;110 }