HDU_3395
我们可以把一条鱼拆成两个点分别代表攻击和被攻击，然后按题意对G[i][j]==1的边的权值设为value[i] ^ value[j]，之后用KM算法求二分图的最优匹配即可。
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define INF 1000000000
int yM[MAXD], G[MAXD][MAXD], N, value[MAXD];
int A[MAXD], B[MAXD];
int visx[MAXD], visy[MAXD], slack;
char b[MAXD];
int init()
{
int i, j;
scanf("%d", &N);
if(!N)
return 0;
for(i = 0; i < N; i ++)
scanf("%d", &value[i]);
for(i = 0; i < N; i ++)
{
scanf("%s", b);
for(j = 0; j < N; j ++)
{
G[i][j] = b[j] - '0';
if(G[i][j])
G[i][j] = (value[i] ^ value[j]);
}
}
return 1;
}
int searchpath(int u)
{
int v, temp;
visx[u] = 1;
for(v = 0; v < N; v ++)
if(!visy[v])
{
temp = A[u] + B[v] - G[u][v];
if(temp == 0)
{
visy[v] = 1;
if(yM[v] == -1 || searchpath(yM[v]))
{
yM[v] = u;
return 1;
}
}
else if(temp < slack)
slack = temp;
}
return 0;
}
void KM()
{
int i, j, u;
for(i = 0; i < N; i ++)
{
A[i] = 0;
for(j = 0; j < N; j ++)
if(G[i][j] > A[i])
A[i] = G[i][j];
}
memset(B, 0, sizeof(B));
memset(yM, -1, sizeof(yM));
for(u = 0; u < N; u ++)
for(;;)
{
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
slack = INF;
if(searchpath(u))
break;
for(i = 0; i < N; i ++)
{
if(visx[i])
A[i] -= slack;
if(visy[i])
B[i] += slack;
}
}
}
void printresult()
{
int i, res = 0;
for(i = 0; i < N; i ++)
res += G[yM[i]][i];
printf("%d\n", res);
}
int main()
{
while(init())
{
KM();
printresult();
}
return 0;
}