match和walk当场AC，travel不会，所以不贴了～
clear:
[cpp]
#include
#include
#include
#include
#include
#include
#define uns unsigned
#define int64 long long
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define oo 0x13131313
#define REP(i, n) for (i = 0; i < (n); ++i)
using namespace std;
int A, B, C, D;
bool a[18][300][300];
char sum[300][300];
int mark, vst[300], cp[300], ans = oo;
struct edge { int t; edge *n; } edges[500], *adj = edges, *lst[300];
bool getbool()
{
char c = getchar();
for (; c != '0' && c != '1'; c = getchar());
return c == '1';
}
bool hun(int x)
{
for (edge *e = lst[x]; e; e = e->n)
if (vst[e->t] != mark)
if (vst[e->t] = mark, !cp[e->t] || hun(cp[e->t]))
return cp[e->t] = x, 1;
return 0;
}
void check(int base)
{
int i, j, res = 0;
adj = edges, memset(lst, 0, sizeof lst);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
if (sum[i][j])
*adj = (edge){j, lst[i]}, lst[i] = adj++;
memset(cp, 0, sizeof cp);
for (i = 1; i <= B; ++i)
++mark, res += hun(i);
if (res + base < ans)
ans = res + base;
}
void dfs(int x, int base)
{
if (x > A) return check(base);
dfs(x + 1, base);
int i, j;
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] -= a[x][i][j];
dfs(x + 1, base + 1);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] += a[x][i][j];
}
int main()
{
int i, j, k;
for (scanf("%d", &D); D--; ) {
scanf("%d%d%d", &A, &B, &C);
int mini = min(A, min(B, C));
memset(sum, 0, sizeof sum);
for (i = 1; i <= A; ++i)
for (j = 1; j <= B; ++j)
for (k = 1; k <= C; ++k)
if (A == mini)
sum[j][k] += a[i][j][k] = getbool();
else if (B == mini)
sum[i][k] += a[j][i][k] = getbool();
else
sum[i][j] += a[k][i][j] = getbool();
if (B == mini)
swap(A, B);
else if (C == mini)
swap(A, C), swap(B, C);
ans = oo;
dfs(1, 0);
printf("%d\n", ans);
}
}
#include
#include
#include
#include
#include
#include
#define uns unsigned
#define int64 long long
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define oo 0x13131313
#define REP(i, n) for (i = 0; i < (n); ++i)
using namespace std;
int A, B, C, D;
bool a[18][300][300];
char sum[300][300];
int mark, vst[300], cp[300], ans = oo;
struct edge { int t; edge *n; } edges[500], *adj = edges, *lst[300];
bool getbool()
{
char c = getchar();
for (; c != '0' && c != '1'; c = getchar());
return c == '1';
}
bool hun(int x)
{
for (edge *e = lst[x]; e; e = e->n)
if (vst[e->t] != mark)
if (vst[e->t] = mark, !cp[e->t] || hun(cp[e->t]))
return cp[e->t] = x, 1;
return 0;
}
void check(int base)
{
int i, j, res = 0;
adj = edges, memset(lst, 0, sizeof lst);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
if (sum[i][j])
*adj = (edge){j, lst[i]}, lst[i] = adj++;
memset(cp, 0, sizeof cp);
for (i = 1; i <= B; ++i)
++mark, res += hun(i);
if (res + base < ans)
ans = res + base;
}
void dfs(int x, int base)
{
if (x > A) return check(base);
dfs(x + 1, base);
int i, j;
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] -= a[x][i][j];
dfs(x + 1, base + 1);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] += a[x][i][j];
}
int main()
{
int i, j, k;
for (scanf("%d", &D); D--; ) {