很久沒有A題了，最近恢復(fù)訓(xùn)練，找回舊日的激情。拿幾個(gè)圖論題目練練手。
解法:很裸的KM最大權(quán)匹配，好久沒敲了，有點(diǎn)忘記了。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 105
#define INF 1 << 29
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a > b ? b : a)
int g[N][N], lx[N], ly[N], match[N];
bool x[N], y[N];
bool dfs(int u, int n)
{
x[u] = 1;
for(int i = 1; i <= n; i++)
{
int wt = lx[u] + ly[i] - g[u][i];
if(!y[i] && !wt)
{
y[i] = 1;
if(match[i] == -1 || dfs(match[i], n))
{
match[i] = u;
return 1;
}
}
}
return 0;
}
int KM(int n)
{
memset(ly, 0, sizeof(ly));
memset(match, -1, sizeof(match));
for(int i = 1; i <= n; i++)
{
lx[i] = -INF;
for(int j = 1; j <= n; j++)
{
lx[i] = MAX(lx[i], g[i][j]);
}
}
for(int k = 1; k <= n; k++)
{
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
while(!dfs(k, n))
{
int d = INF;
for(int i = 1; i <= n; i++)
if(x[i])
for(int j = 1; j <= n; j++)
if(!y[j])
d = MIN(d, lx[i] + ly[j] - g[i][j]);
for(int i = 1; i <= n; i++)
{
if(x[i]) lx[i] -= d, x[i] = 0;
if(y[i]) ly[i] += d, y[i] = 0;
}
}
}
int sum = 0;
for(int i = 1; i <= n; i++)
sum += g[match[i]][i];
return sum;
}
int main()
{
int n, v[N], ans;
char str[N];
while(scanf("%d", &n), n)
{
memset(g, 0, sizeof(g));
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for(int i = 1; i <= n; i++)
{
scanf("%s", &str);
for(int j = 0; j < n; j++)
{
if('1' == str[j])
{
g[i][j + 1] = v[i] ^ v[j + 1];
}
}
}
ans = KM(n);
printf("%d\n", ans);
}
return 0;
}